这两天专门训练了backtracking类型的问题，包括N皇后、全排列全组合等等，我到现在也无法完全清晰描述recursive里的运行过程，但是多做了几道这种类型的题目之后发现还是很有套路的，即使思路不是很清晰也可以“凑”出代码。
recursive的代码有两点关键：1.出口条件 2.循环的写法
出口条件：出口条件还是挺容易，如全排列中list的长度为nums的length就把它加入到result list中，比如combination中sum等于target
循环的写法：
1.全排列中用for (int i = 0; i < mums.length; i ++), 全组合中用for (int i = index; i < mums.length; i ++),用一个visited数组来记录元素是否被访问过，if (visited[I] == true) continue;
2.如何处理有重复的情况？首先均需经过sort的预处理，全组合去除重复组合的写法: if (i > index && nums[i] == nums[i-1]) continue; 全排列去除重复组合的方法：if (i > 0 && nums[i] == nums[i-1] && visited[i-1] == false) continue;
转载请注明：XAMPP中文组官网 » 用Backtracking思想解决subset/permutation/combination/partition问题