题目链接：
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 > subsets(int[] nums) { 3 4 List > res = new ArrayList<>(); 5 List item = new ArrayList<>(); 6 Arrays.sort(nums); 7 dfs(res,item,nums,0); 8 return res; 9 10 }11 public void dfs(List > res,List item,int []nums,int start)12 {13 14 res.add(new ArrayList<>(item));15 16 for(int i=start;i
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 > subsetsWithDup(int[] nums) { 3 List > res = new ArrayList<>(); 4 5 List item = new ArrayList<>(); 6 Arrays.sort(nums); 7 dfs(res,item,nums,0); 8 9 return res;10 }11 12 public void dfs(List > res,List item,int []nums,int start)13 {14 if(!res.contains(item))//就多了这一行，！！！如果出现了就不加进去15 res.add(new ArrayList<>(item));16 17 for(int i=start;i
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 > permute(int[] nums) { 4 5 List > res = new ArrayList<>(); 6 List 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 > res,List item,int []nums)15 {16 if(item.size()==nums.length)17 {18 res.add(new ArrayList<>(item));19 20 }21 else22 {23 for(int i=0;i
1 import java.util.ArrayList; 2 class Solution { 3 public List > permute(int[] nums) { 4 5 List > res = new ArrayList<>(); 6 List 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 > res,List item,int []nums,boolean []used)17 {18 if(item.size()==nums.length)19 {20 res.add(new ArrayList<>(item));21 22 }23 else24 {25 for(int i=0;i
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 > permuteUnique(int[] nums) { 3 List > res = new ArrayList<>(); 4 List 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 > res,List 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 else22 {23 for(int i=0;i
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 > combinationSum(int[] candidates, int target) { 4 5 List > res= new ArrayList<>(); 6 List 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 > res,List item,int start,int target,int []candidates)18 {19 if(target<0)20 return ;21 if(target==0)22 {23 res.add(new ArrayList (item));24 }25 26 for(int i=start;i
1 import java.util.ArrayList; 2 class Solution { 3 public List > combinationSum2(int[] candidates, int target) { 4 5 List > res= new ArrayList<>(); 6 List 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 > res,List 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 (item));26 }27 }28 29 for(int i=start;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 Permutation(String str) { 5 ArrayList 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 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 else32 {33 for(int i=0;i