对于dfs剪枝的分析

剑指 Offer 38. 字符串的排列

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:

输入：s = “abc” 输出：[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]

限制：

1 <= s 的长度 <= 8 通过次数91,188 提交次数162,110 请问您在哪类招聘中遇到此题？
本书精选谷歌、微软等知名IT企业的典型面试题，系统地总结了如何在面试时写出高质量代码，如何优化代码效率，以及分析、解决难题的常用方法。

dfs我们并不陌生，但是当题目涉及到剪枝的dfs就没那么容易了。
当然其效率也天差地别。

剪枝相比于不剪枝，效率提升了四倍

那么该如何剪枝呢？

我们需要先分析，究竟是为什么是导致了dfs效率低下。

我们先看dfs代码，结合代码分析‘112’的重复枝都在哪里产生。

bool book[10]; 
vector<string > v;

void dfs(string s, string t){
	if(s.length()==t.length()){
		v.push_back(t);
		return ;
	}
	for(int i=0;i<s.length();i++){
		if(book[i])
			continue;
		book[i] = true;
		dfs(s,t+s[i]);
		book[i] = false;
	}	
}

如图所示，这是dfs过程中对“112”所生成的所有递归树。

很明显的看到根节点为root的树有两科重复的子树，既然是重复的子树，则递归形成的先序遍历结果必然相同。
同理，根节点为2的树也两颗相同的子树，正是因为有这些重复子树的原因，导致不得不花费时间和空间开销来
消除重复序列。

我们的想法就是，想办法让重复子树只出现一次，这样就能节省很大的时间开销。

通过观察和分析，我们不难发现两棵子树如果根节点相同，则这两颗子树必相同。

其原理是，构成子树节点的元素一定来自于未被祖先节点使用过元素组成。如果两颗子树的根节点相同，那么他
们的子树节点元素集合一定相同，故两者的排列组合集合也一定相同。（类似于传递闭包概念）

故 我们只需要剪掉一个节点下相同的孩子节点所在的子树就可以了。
代码如下：

bool book[10]; 
vector<string > v;

void dfs(string s, string t){
	if(s.length()==t.length()){
		v.push_back(t);
		return ;
	}
	**bool visited[255];**
	**memset(visited,0,sizeof(visited));**
	for(int i=0;i<s.length();i++){
		if(book[i]**||visited[s[i]]**)
			continue;
		book[i] = true;
		visited[s[i]] = true;
		dfs(s,t+s[i]);
		book[i] = false;
	}	
}