78，90，Subsets，46，47，Permutations，39,40 DFS 大合集

题目链接：

78：

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets. 集合里面没有重复的，比如没有[1,2]和[2,1]，所以最好最好先对nums排个序是最好的

Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

解题思路：深度优先搜索，

这里是经典回溯法解决问题，new ArrayList<>(item)这里是相当于new了一个新对象，不是在原始的对象上操作。

我会把所有的用回溯的题全部放在一起

Subset这道题的条件比较直观，就是每当我们添加了一个元素，都是一个新的子集。那么我们怎么保证不会出现重复集合呢。我们引入一个int pos用来记录此子集的起点在哪，比如当pos = 1的时候就是从第二个元素往后循环添加元素（0 base）,每次当此层用了第i个元素，那么下一层需要传入下一个元素的位置i+1 除此之外，当循环结束要返回上一层dfs的时候我们需要把这一层刚添加元素删去。

比如输入集合为［1，2，3］应当是这么运行，

[]

[1]

[1,2]

[1,2,3] //最底层子循环到头返回删去3，上一层的子循环也到头删去2

//而此时，这一层循环刚到2，删去后还可以添加一个3

[1,3] //删除3，删除1

[2]

[2,3] //删除3，删除2

[3]

 1 class Solution {
 2     public List<List<Integer>> subsets(int[] nums) {
 3         
 4         List<List<Integer>> res = new ArrayList<>();
 5         List<Integer> item = new ArrayList<>();
 6         Arrays.sort(nums);
 7         dfs(res,item,nums,0);
 8         return res;
 9         
10     }
11     public void dfs(List<List<Integer>> res,List<Integer> item,int []nums,int start)
12     {
13         
14         res.add(new ArrayList<>(item));
15         
16         for(int i=start;i<nums.length;i++)
17         {
18             item.add(nums[i]);
19             dfs(res,item,nums,i+1);
20             item.remove(item.size()-1);
21         }
22         
23     }
24 }

90：Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets. 同样的，求子集合，虽然有重复的元素，但是不能有[1,2] 和[1,2]，最好也是先排序，然后发现res里面如果出现重复的就不加进去。多了一行

Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Example:

 1 class Solution {
 2     public List<List<Integer>> subsetsWithDup(int[] nums) {
 3         List<List<Integer>> res = new ArrayList<>();
 4         
 5         List<Integer> item = new ArrayList<>();
 6         Arrays.sort(nums);
 7         dfs(res,item,nums,0);
 8         
 9         return res;
10     }
11     
12     public void dfs(List<List<Integer>> res,List<Integer> item,int []nums,int start)
13     {
14         if(!res.contains(item))//就多了这一行，！！！如果出现了就不加进去
15             res.add(new ArrayList<>(item));
16         
17         for(int i=start;i<nums.length;i++)
18         {
19             item.add(nums[i]);
20             dfs(res,item,nums,i+1);
21             item.remove(item.size()-1);
22         }
23         
24     }
25 }

46：这里有个建议：求数组的全排列，最好都用一个used数组来判断是否已经访问过这个元素来做方便，就不用记很多的套路了。所以46和47 的d代码一模一样的。！！！

Given a collection of distinct integers, return all possible permutations.

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

解题思路：

这个题目是求一组不同整数的全排列，也是用DFS做

 1 import java.util.ArrayList;
 2 class Solution {
 3     public List<List<Integer>> permute(int[] nums) {
 4         
 5         List<List<Integer>> res  = new ArrayList<>();
 6         List<Integer> item = new ArrayList<>();
 7         
 8         if(nums==null||nums.length==0)
 9             return res;
10         Arrays.sort(nums);
11         boolean []used = new boolean[nums.length];
12         dfs(res,item,nums,used);
13         return res;
14     }
15     
16     public void dfs(List<List<Integer>> res,List<Integer> item,int []nums,boolean []used)
17     {
18         if(item.size()==nums.length)
19         {
20             res.add(new ArrayList<>(item));
21             
22         }
23         else
24         {
25             for(int i=0;i<nums.length;i++)
26             {
31                 if(!used[i])
32                 {
33                      used[i] = true;
34                     item.add(nums[i]);
35                     dfs(res,item,nums,used);
36                     item.remove(item.size()-1);   
37                     used[i] = false;         
38                 }
39             }
40         }
41     }
42     
43 
44 }

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Example:这里要用一个used数组来判断，是不是已经访问过这个元素了。然后再去重一遍

 1 class Solution {
 2     public List<List<Integer>> permuteUnique(int[] nums) {
 3         List<List<Integer>> res  = new ArrayList<>();
 4         List<Integer> item = new ArrayList<>();
 5         if(nums==null||nums.length==0)
 6             return res;
 7         Arrays.sort(nums);
 8         boolean [] used  = new boolean[nums.length];
 9         
10         dfs(res,item,nums,used);
11         return res;
12     }
13     
14     public void dfs(List<List<Integer>> res,List<Integer> item,int []nums,boolean []used)
15     {
16         if(item.size()==nums.length && !res.contains(item))
17         {
18             res.add(new ArrayList<>(item));
19             
20         }
21         else
22         {
23             for(int i=0;i<nums.length;i++)
24             {
25                 if(!used[i])
26                 {
27                     item.add(nums[i]);
28                     used[i] = true;
29                     dfs(res,item,nums,used);
30                     item.remove(item.size()-1);  
31                     used[i] = false;
32                     
33                 }             
34             }
35         }
36     }
37 }

39. Combination Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

这两个题目一模一样，区别在意一个可以重复利用数字，一个不可以。所以代码也一样的，就差了helper(res,item,i+1,newtarget,candidates);还有一个是i

 1 import java.util.ArrayList;
 2 class Solution {
 3     public List<List<Integer>> combinationSum(int[] candidates, int target) {
 4         
 5         List<List<Integer>> res= new ArrayList<>();
 6         List<Integer> item = new ArrayList<>();
 7         
 8         if(candidates==null||candidates.length==0)
 9             return res;
10         
11         Arrays.sort(candidates);
12         
13         helper(res,item,0,target,candidates);
14         
15         return res;
16     }
17     public void helper( List<List<Integer>> res,List<Integer> item,int start,int target,int []candidates)
18     {
19         if(target<0)
20             return ;
21         if(target==0)
22         {
23             res.add(new ArrayList<Integer>(item));
24         }
25         
26         for(int i=start;i<candidates.length;i++)
27         {
28             item.add(candidates[i]);
29             int newtarget = target - candidates[i];
30             helper(res,item,i,newtarget,candidates);
31             ////先加入元素，然后进行搜索，这里进行DFS搜索，如果不满足，就把temp列表里的元素去除掉
32             item.remove(item.size()-1); 
33             ////目标和不符合，所以将临时列表的最新值去除，然后尝试下一个元素
34         }
35     }
36 }

 1 import java.util.ArrayList;
 2 class Solution {
 3     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
 4         
 5         List<List<Integer>> res= new ArrayList<>();
 6         List<Integer> item = new ArrayList<>();
 7         
 8         if(candidates==null||candidates.length==0)
 9             return res;
10         
11         Arrays.sort(candidates);
12         
13         helper(res,item,0,target,candidates);
14         
15         return res;
16     }
17     public void helper( List<List<Integer>> res,List<Integer> item,int start,int target,int []candidates)
18     {
19         if(target<0)
20             return ;
21         if(target==0)
22         {
23             if(!res.contains(item))
24             {
25                 res.add(new ArrayList<Integer>(item));
26             }
27         }
28         
29         for(int i=start;i<candidates.length;i++)
30         {
31             if(i>start && candidates[i]==candidates[i-1]) 
32                 continue;
33             item.add(candidates[i]);
34             int newtarget = target - candidates[i];
35             helper(res,item,i+1,newtarget,candidates);
36             ////先加入元素，然后进行搜索，这里进行DFS搜索，如果不满足，就把temp列表里的元素去除掉
37             item.remove(item.size()-1); 
38             ////目标和不符合，所以将临时列表的最新值去除，然后尝试下一个元素
39         }
40     }
41 }

 
剑指offer字符串的全排列

 1 import java.util.ArrayList;
 2 import java.util.Collections;
 3 public class Solution {
 4     public ArrayList<String> Permutation(String str) {
 5        ArrayList<String> res = new ArrayList<>();
 6         
 7        StringBuffer item  = new StringBuffer();
 8         
 9         if(str.length()==0)
10             return res;
11         boolean []used = new boolean[str.length()];
12         fun(str.toCharArray(),res,item,used);
13         
14         Collections.sort(res);
15         return res;
16     }
17     
18     public void fun(char[]ch,ArrayList<String> res,StringBuffer item,boolean []used)
19     {
20        
21         if(item.length()==ch.length)
22         {
23             String x = item.toString();
24             if(!res.contains(x))
25             {
26                 res.add(x);
27                 
28                 item = new StringBuffer(item);
29             }
30         }
31         else
32         {
33             for(int i=0;i<ch.length;i++)
34             {
35                 if(!used[i])
36                 {
37                     used[i]=true;
38                     item.append(ch[i]);
39                     fun(ch,res,item,used);
40                     item.deleteCharAt(item.length()-1);
41                     used[i] = false;
42                     
43                 }
44             }
45         }
46     }
47 
48 }