题目链接：
https://leetcode.com/problems/subsets/
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 if(nums==null||nums.length==0)
8 return res;
9 Arrays.sort(nums);
10 dfs(res,item,nums);
11 return res;
12 }
13
14 public void dfs(List<List<Integer>> res,List<Integer> item,int []nums)
15 {
16 if(item.size()==nums.length)
17 {
18 res.add(new ArrayList<>(item));
19
20 }
21 else
22 {
23 for(int i=0;i<nums.length;i++)
24 {
25 // if(!item.contains(nums[i]))
26 // item.add(nums[i]);为什么不用这个，因为我不跳过，就会一直执行这个循环
27 if(item.contains(nums[i]))
28 continue;
29 item.add(nums[i]);
30 dfs(res,item,nums);
31 item.remove(item.size()-1);
32 }
33 }
34 }
35
36
37 }
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 {
27 // if(!item.contains(nums[i]))
28 // item.add(nums[i]);为什么不用这个，因为我不跳过，就会一直执行这个循环
29 // if(item.contains(nums[i]))
30 // continue;
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 }