Leetcode刷题记录（数组）组合总和、组合总和 II

真是好久没刷题，好久没写博客了，最怪的是最近也没忙什么，秋招在即，此篇仅记录刷题过程，为以后复习做准备
一、组合总和
这道题是个典型的DFS，通过选和不选两种状态进行深搜，由于一个数可以不限次数的选取，所以在递归中，下标无需加一

class Solution {
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
    
        List<Integer> item = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        dfs(candidates,target,item,ans,0);
        return ans;
    }
    public void dfs(int[] candidates, int target,List<Integer> item,List<List<Integer>> ans,int index){
    
        if(index == candidates.length){
    
            return ;
        }
        if(target == 0){
    
            ans.add(new ArrayList(item));
            return ;
        }
        //不选
        dfs(candidates,target,item,ans,index+1);
		//选
        if(target-candidates[index] >= 0){
    
            item.add(candidates[index]);
            dfs(candidates,target-candidates[index],item,ans,index);
            item.remove(item.size()-1);
        }
    
    }
}

二、组合总和 II
这道题比上题多加了个限制，就是每一个数只能用一次，并且不能包含重复的集合
1、每一个数用一次：这个只需要在每次递归时让index++就能解决，选取了当前数，就不能在选这个数了
2、不能包含重复的集合：这个我们可以先将数组排好序，在每一层循环中只能选择一种数，例如：1 1 1 2 2 这组数，在第一层循环中如果选择了第一个1，那么就不能选择第二个1，下次选择满足条件的话就只能选择2，不然就会造成重复的问题

class Solution {
    
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    
        List<Integer> item = new ArrayList<>();
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);
        dfs(candidates,target,item,ans,0);
        return ans;
    }
    public void dfs(int[] candidates, int target,List<Integer> item,List<List<Integer>> ans,int index){
    
        if(target == 0){
    
            ans.add(new ArrayList(item));
            return ;
        }
        for(int i = index ; i <candidates.length ; i++){
    
            if(i!=index&&candidates[i]==candidates[i-1]){
    //防止同一层循环宣选到一样的数
                continue;
            }
            if(target - candidates[i] >= 0){
    
            item.add(candidates[i]);
            dfs(candidates,target-candidates[i],item,ans,i+1);
            item.remove(item.size()-1);
            }
        } 
    }
}