combination sum、permutation、subset(组合和、全排列、子集)

combination sum I、permutation I、subsets  I 是组合和、全排列、子集的第一种情况，给定数组中没有重复的元素。

combination sum II、permutation II、subsets  II 是组合和、全排列、子集的第而种情况，给定数组中有重复元素。

combination sum I中元素每个可以被多次使用，所以每次遍历都是从当前元素开始，然后往后面遍历。

combination sum II中元素只能被使用一次，所以算下个元素时，只能从当前元素后面的元素查找。

全排列每次都要从头开始遍历，既然从头遍历，就要考虑前面元素是否使用过。对于permutation I，每次从头遍历只要判断当前元素是否使用过，这个可以使用list.contains判断，也可以使用combination sum II而中的数组来表示是否使用过。因为全排列每次从头遍历，而且添加时不能添加那些已经在集合中的元素（使用过的），所以用一个数组。而从当前元素下一个开始遍历的情况（求子集），则不需要考虑前面的元素，只考虑后面的，而后面的元素都是没有使用过的，所以不需要再判断是否使用过，只需要考虑跳过重复元素就行。

求子集是每次要从当前元素后面的元素添加，也就是遍历当前元素后面的元素。subsets  I不需要判断是否重复，也不需要排序。判断条件只是list中元素个数小于nums长度即可，也就是是集合之一，但是判断完了不返回，因为还有继续添加。subsets  II则要排序，还有去除重复元素，这里跳过重复元素并不需要额外数组，因为不是从头开始，只要跳过相同的即可。

注意这几个处理重复的方法：全排列是用到所有元素，每次从头遍历，所以它处理重复的方法就是使用一个数组标记是否使用过该元素。子集和组合不是从头开始遍历，每次只遍历后面的元素，它的处理方式就是直接用if跳过相同元素。

代码：

combination sum I

class Solution {
public List<List<Integer>> combinationSum(int[] nums, int target) {
   /**
   这个题是穷举所有情况，回溯的可能性比较大
   */
        Arrays.sort(nums);
    List<List<Integer>> result=new ArrayList<List<Integer>>();
    backtracking(result,new ArrayList<Integer>(),nums,target,0,0);
    return result;
    }
    
    public void backtracking(List<List<Integer>> result,List<Integer> tmp,int[] nums,int target,int sum,int index){
        if(sum>target) return ;
        if(sum==target) {
            result.add(new ArrayList<Integer>(tmp));
            return ;
        }
        
        if(index>nums.length-1) return ;
        
        for(int i=index;i<nums.length;i++){
            tmp.add(nums[i]);
            backtracking(result,tmp,nums,target,sum+nums[i],i);
            tmp.remove(tmp.size()-1);
        }
    }
}

combination sum II

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> result=new ArrayList<List<Integer>>();
        if(candidates==null||candidates.length==0) return result;
        Arrays.sort(candidates);
        backtracking(result,new ArrayList<Integer>(),candidates,target,0,0);
        return result;
    }
    
    public void backtracking(List<List<Integer>> result,List<Integer> list,int[] nums,int target,int sum,int index){
        if(sum>target) return ;
        if(sum==target){
            result.add(new ArrayList<Integer>(list));
            return ;
        }
        if(index>nums.length-1) return ;
        /*
        这一题相比combination sum I,做了两点修改，1、数组中每个元素只能被使用一次；2、数组中有重复元素。针对1，每次添加list从下一个元素开始（i+1）；针对2，每次遍历的时候，跳过重复的元素。
        */
        for(int i=index;i<nums.length;i++){
            //每次遍历时，跳过重复元素，这样就不会出现重复的两个list
            if(i>index&&nums[i]==nums[i-1]) continue;  
            list.add(nums[i]);
            backtracking(result,list,nums,target,sum+nums[i],i+1);
            list.remove(list.size()-1);
        }
    }
}

permination I

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if(nums.length<=0) return result; 
        backtracking(result,new ArrayList<Integer>(),nums);
        return result;
    }
    
    public void backtracking(List<List<Integer>> result, List<Integer> list,int[] nums){
        if(list.size()==nums.length){
            result.add(new ArrayList<Integer>(list));
            return ;
        }
        
        for(int i=0;i<nums.length;i++){
            if(list.contains(nums[i])) continue;//每次都是遍历数组中的每个元素，然后添加不一样的元素（保证不重复）
            list.add(nums[i]);
            
            backtracking(result,list,nums);
            list.remove(list.size()-1);
            
        }
    }
}

permination II

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        if(nums==null||nums.length==0) return res;
        //该数组用来标记每个位置的元素是否使用以保证每个位置的元素只能使用一次。控制递归遍历（往list后面添加元素）中该元素是否已经使用。
        boolean[] used=new boolean[nums.length];
        Arrays.sort(nums);
        List<Integer> list=new ArrayList<>();
        helper(nums,res,list,used);
        return res;
    }
    
    public void helper(int[] nums,List<List<Integer>> res,List<Integer> list,boolean[] used){
        if(nums.length==list.size()){
            res.add(new ArrayList<Integer>(list));
            return ;
        }
        for(int i=0;i<nums.length;i++){
            if(used[i]) continue;  //该元素使用过了。
            //下一个重复值只有在前一个重复值被使用的情况下才可以使用。
            /*
　　　    这个!used[i-1]条件是为深度遍历准备的。
           对于当前层遍历时，每遍历一个元素结束后就会设为false然后遍历下一个，所以可以跳过重复元素，避免相同元素出现在同一个位置。
            对于深度遍历（递归，往结果集中继续添加元素），需要使用!used[i-1]来保证后面的相同元素可以往后面的结果集中添加。
　　　　　　比如[1,1,2].第一层遍历第一个1时，设为true后，递归往后面添加第二个元素，此时也是从第一个元素开始遍历，
　　　　　　因为此时used[0]为true,所以跳过，i=1，此时如果没有!used[i-1]，也会跳过第二个1了，所以需要加上这个条件。
　　　　　　
　　　　　　*/

            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;
            used[i]=true;
            list.add(nums[i]);
            helper(nums,res,list,used);
            //下面这两步，为了同层遍历，同层遍历是给一个位置轮流添加元素。所以需要将上一个添加的元素删了,然后删除标记，遍历下一个元素
            used[i]=false;
            list.remove(list.size()-1);
        }
    }
}

subsets I

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        if(nums==null||nums.length==0) return res;
        helper(res,new ArrayList<Integer>(),nums,0);
        return res;
    }
    
    public void helper(List<List<Integer>> res,List<Integer> list,int[] nums,int index){
        if(list.size()<=nums.length){
            res.add(new ArrayList<Integer>(list));
        }
        for(int i=index;i<nums.length;i++){
            list.add(nums[i]);
            helper(res,list,nums,i+1);
            list.remove(list.size()-1);
        }
    }
}

subsets II

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res=new ArrayList<List<Integer>>();
        if(nums==null||nums.length==0) return res;
        Arrays.sort(nums);  //有相同元素，所以要排序
        helper(res,new ArrayList<Integer>(),nums,0);
        return res;
    }
    public void helper(List<List<Integer>> res,List<Integer> list,int[] nums,int index){
        //求子集，所以判断条件为.而且满足条件后还要继续向下进行，而不是返回
        if(list.size()<=nums.length)
            res.add(new ArrayList<Integer>(list));
        for(int i=index;i<nums.length;i++){
            //跳过相同的元素。因为是从后面的元素中选元素，不是从头开始，所以不需要再创建是否使用的数组了。注意：下面是i>index，而不是i>0.
            if(i>index&&nums[i]==nums[i-1]) continue;  
            list.add(nums[i]);
            helper(res,list,nums,i+1);
            list.remove(list.size()-1);
        }
    }
}