subset-DFS+Backtracking系列，有模板方法可以记
例1：leetcode 78. Subset
1. 题目分析
- 首先 ，这个题是NP问题，没有多项式时间内的算法，只能用搜索解决的问题
- 选择用DFS-backtracking 的递归方式解决
- 画递归树图
- 搜索问题中处理去重：选代表（改题我们遇到重复的，选择留下有序的），因为我们的递归helper是在index向后排的时候调用，（因为树没有重复，我们枚举元素都是按照顺序的，所以不会有答案出现重复）或者看本题的code中，start就是起到了去重作用的，每次都从start下一个开始
(tips: - 题目中说找出所有子集，所有可能这种，大部分都靠搜索解决
- 去重的误区：找到所有答案，再按要求去重，比如：[1,1,1,1,1,1]找所以子集，其实只有lengh+1个，但如果找所有子集，就太多了，
)
2. 代码实现思路
- 先排除边界情况：判断输入的array nums 是不是有效的，这里做判断：
if nums==null||nums.length==0{return results};(results是刚初始化的返回值) - 写递归：
- 递归定义：以subset开头的所有自己放在result里（从nums里的startindex开始挑数）
- 递归的拆解
- 递归的出口、什么时候记录答案：if(){return;},这里不需要出口，要一直做到没有就退出
3. 时间复杂度分析
通用时间复杂度：O(解的个数 * 每个解产生的复杂度)，数学推导有兴趣的话 可以看这个帖子，http://www.jiuzhang.com/qa/1601/
subset
=O(2^n * n) 构造每个答案的时间是1，2，。。。n平均就是n/2，就是n
permutation
=O(nn!) n!个答案
n queens 不知道有几个答案
=O(ns) s 是答案的个数
4. code
class Solution {
/**
* @param S: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public ArrayList<ArrayList<Integer>> subsets(int[] nums) {
if(nums==null||nums.length==0) return null;
ArrayList<ArrayList<Integer>> results = new ArrayList<>();
//把空集开头的所有集合放入result
dfsHelper(nums,0,new ArrayList<Integer>(), results);
return results;
}
private void dfsHelper(int[] nums,
int startIndex,
ArrayList<Integer> subset,
ArrayList<ArrayList<Integer>> results){
//deep copy,否则后面操作subset，subset的内容就改变了
results.add(new ArrayList<Integer>(subset));
for(int i = startIndex; i<nums.length;i++){
subset.add(nums[i]);
dfsHelper(nums,i+1,subset,results);
subset.remove(subset.size()-1);
}
}
}
5. 一些细节
- 库函数 Arrays.sort()是用的quick sort实现，可以认为是nlogn的复杂度
- 代码中写的deep copy，java默认都是pass by reference ，这里不new的话传递的是指向subset的reference，后面subset改变，results中加入的subset也会改变，最后返回就变成了[[],[],[],[]......]
- 这里不可以用results.addAll(xxx) ，因为addAll 表示，把xxx中的元素都加入到results中，我们是需要加入list，而不是list中的元素
- 为什么result.add 在for循环前面？
因为答案不仅仅只存在于搜索树的叶子节点，每一个节点都是一个答案，所以进入这个搜索节点 就要add一下 - 要记得递归完成后subset.remove(subset.size() - 1)，这就是BackTracking，把刚才加进去的那一个清除掉（add--remove） ，回到上一步，再继续向后进行，刚才添加进去的那个就是idx=subset.size() - 1，因为我们是往list添加元素，那么当前元素就是添加在list后面，我们回溯是一层一层上来，就是从后一层一层把元素remove掉，当前就remove目前的最后的元素
- DFS有两种实现方式，一种是递归，一种是非递归，递归只算作是一种实现的方式
例2 Leetcode 90. Subsets II
1. 题目分析
- 出现了找出所有子集的关键字，所以还是用搜索
- 跟上题不一样的是 input数组中有重复元素
2. 代码实现思路
跟上题一样，除了：
如何去重，比如输入[1,2,2] list长=1的只有两个了[1]，[2]。我们可以通过选代表的方式来决定，放入第一个2，所以我们要做的就是在放入第一个2之前，不能放第二个2，
- 这里首先需要通过排序把相等的数凑在一起
- 再在helper中，for loop中，
if(i>start&&nums[i]==nums[i-1]) continue;的那句话，i>start 说明start这个元素在i前面，应该被先加入子集，但却没有加入。进入递归前，加入的元素是i，传入的start=i+1, 递归中的i==start，刚好加入subset，如果i>start，说明I前面的还没有加入subset
3. 时间复杂度分析
O(n^2)
4. code
public class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if(nums==null||nums.length==0) return results;
Arrays.sort(nums);
ArrayList<Integer> subset = new ArrayList<>();
dfsHelper(0,nums,subset,results);
return results;
}
private void dfsHelper(int start, int[] nums, ArrayList<Integer> subset, List<List<Integer>> results){
results.add(new ArrayList(subset));
for(int i = start; i<nums.length; i++){
if(i>start&&nums[i]==nums[i-1]) continue;
subset.add(nums[i]);
dfsHelper(i+1,nums,subset,results);
subset.remove(subset.size()-1);
}
}
}
5. 一些细节
subset2 需要注意。。
continu用法？这个太初级了吧，最需要注意的就是 for循环递归调用前的if判断
例3： permutation
46. Permutations
（先是一段碎碎念：背会了subset也不会写permutation，好烦躁。这个题可以看出和subset的区别是 拼完之后才放入result中，所以就想helper之后再results.add，但走了条错路，正确的思路是，跟以前一样开始helper的时候result.add不同的是只有当subset==nums.length才添加这个subset. 又挣扎了一会儿发现就算写在后面也可以，写在后面跑一遍发现还是添加了subset那么多东西，就想到要要等三个了在加入results，再想到判断subset大小满足条件才添加，一样可以ac。。。一直觉得递归很难想可能就在于，我怎么都想不到在helper刚进入的时候添加上一次的subset，顶多能看懂，自己想总是把添加操作想在后面，sign。。）
1. 题目分析
- 如果把所有的recursion问题都想象成一棵树。subset上面每一个树的节点都是结果。而permutation上面只有叶子节点才是结果
2. 代码实现思路
跟subset其实很像，能想到if那句，这个题就解了
3.时间复杂度
recursive的复杂度都不低
这个应该比subset快一点，上面有计算通式，因为解的个数变少了，每个解产生的复杂度是一样的
4. code
//按照subset的格式写的话是这样的
public class Solution {
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if(nums==null||nums.length==0) return results;
List<Integer> subset = new ArrayList<>();
helper(nums,subset,results);
return results;
}
private void helper(int[] nums, List<Integer> subset, List<List<Integer>> results ){
if(subset.size()==nums.length){
results.add(new ArrayList<Integer>(subset));
}else{
for(int i = 0; i< nums.length; i++){
if(subset.contains(nums[i])) continue;
subset.add(nums[i]);
helper(nums,subset,results);
subset.remove(subset.size() - 1);
}
}
}
}
5. 一些细节：
这里舍弃了index的方法，个人觉得不太好想，除非很好的理解搜索和去重，subset中的index是帮助去重的，随着index一直向后推移才保证了不会重复添加之前的子集，而这个题不需要去重，所以根据画递归树的过程可以大致想到，每次都要从头遍历的，但我没想到用size和length比较来判断，想的是result.add放在helper后面不就是等3个都齐了才添加么，由此可见还是对递归了解不够。递归方法完成后会一步一步回到之前的调用者函数。要搞明白流程，画图或者写流程很有帮助
例4：permutation2
1. 题目分析
- 有重复元素后得到的结果少多了。。ye
- 跟上题不一样的是 input数组中有重复元素
2. 代码实现思路
跟上题一样，除了：如何去重，
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;这个判断判断主要是为了去除重复元素影响。
比如，给出一个排好序的数组，[1,2,2]，那么第一个2和第二2如果在结果中互换位置，我们也认为是同一种方案，所以我们强制要求相同的数字，原来排在前面的，在结果当中也应该排在前面，这样就保证了唯一性。所以当前面的2还没有使用的时候，就不应该让后面的2使用。
如果看不懂这句话，找一张大点的纸，按照程序写一下执行流程，执行到第二次放入第一个元素1的时候就明白了。
3. 时间复杂度分析
O(n^2)
4. code
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> results = new ArrayList<>();
if(nums==null||nums.length==0) return results;
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
ArrayList<Integer> subset = new ArrayList<>();
dfsHelper(nums,used,subset,results);
return results;
}
private void dfsHelper( int[] nums, boolean[] used, ArrayList<Integer> subset, List<List<Integer>> results){
if(subset.size()==nums.length){
results.add(new ArrayList<Integer>(subset));
}else{
for(int i = 0; i<nums.length; i++){
if(used[i]) continue;
if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
used[i] = true;
subset.add(nums[i]);
dfsHelper(nums,used,subset,results);
used[i] = false;
subset.remove(subset.size()-1);
}
}
}
}
例5：Combination Sum :
https://leetcode.com/problems/combination-sum/
结果里每种combination都只能出现一次，又每个数字使用次数不限，所以需要去重，（如果不removeDuplicate，也可直接排序一下，不过remove Diplicates应该复杂度低一些）
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
tempList.remove(tempList.size() - 1);
}
}
}
例6：Combination Sum II (can't reuse same element) :
https://leetcode.com/problems/combination-sum-ii/
这题和上题的题目区别在于
Combination sum
- 结果里每种combination都只能出现一次，又每个数字使用次数不限，所以需要去重
- 因为每个数不限出现次数，所以for循环中每次dfs都传i进去，而不再是i+1
- for-loop里还有一点需要注意，target<nums[i] break;
Combination sum2
给定数组中的数字出现几次，combination中总共只能出现几次。也就是每个数只能用一次，当然combinations里还是不能有重复combination。 比如输入是[7,1,2,5,1,6,10], 8，排序后是[1,1,2,5,6,7,10],输出里可以有116，但如果input：1，1，1.target：1， result： 1 不能有三个1的
- 第一次for-loop，i=startIndex=0，combination先添加1，然后继续找，等所有情况找完之后（此时已递归好多次），
- 从下一个元素开始，发现又是1，因为刚才已经把包含1的组合都找过了（因为每个数只能用1次，所以可以和1组成combination的都用过了，所以第二个1没有数可以用了），所以这次不再找，continue；而且如果从这个1再找，可能就会找到跟之前那个1组成的一样的combination，但result里，combination不能重复的。总之就是要跳过了
两道题代码写法的区别有四点：
- 不需要removeDuplicate（如果原题不removeDuplicate，也可直接排序一下，不过remove Diplicates应该复杂度低一些）
- 需要sort（第二题这个是必须sort，没有别的选择）
- 每次dfs开始从i+1，不再是i
- 多一次去重
if(i!=startIdx && candidates[i]==candidates[i-1]) continue;
public List<List<Integer>> combinationSum2(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
例7：Palindrome Partitioning :
https://leetcode.com/problems/palindrome-partitioning/
public List<List<String>> partition(String s) {
List<List<String>> list = new ArrayList<>();
backtrack(list, new ArrayList<>(), s, 0);
return list;
}
public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){
if(start == s.length())
list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < s.length(); i++){
if(isPalindrome(s, start, i)){
tempList.add(s.substring(start, i + 1));
backtrack(list, tempList, s, i + 1);
tempList.remove(tempList.size() - 1);
}
}
}
}
public boolean isPalindrome(String s, int low, int high){
while(low < high)
if(s.charAt(low++) != s.charAt(high--)) return false;
return true;
}
模板
回溯：有过剪枝的DFS过程。比如上面的subset
解答树角度：带回溯的dfs遍历一棵解答树
回溯的一般结构：
void dfs(int 当前状态)
{
if(当前状态为边界状态)
{
记录或输出
return;
}
for(i=0;i
{
//获取各种子状态。
修改全局变量
if(子状态满足条件)
{
dfs(子状态)
}
恢复全局变量--回溯
}
}
BFS：
//将首节点加入队列：
q.push(head);
//标记首节点已访问：
isvisited[head]=true;
while(!q.empty()) {
int temp=q.pop();
//访问temp，并标记temp已被访问过，
//将temp的子相关节点加入队列
q.push(temp相关节点);
}
