Leetcode question brushing record (array) combination sum, combination sum II

I haven't scratched the question for a long time , I haven't written a blog for a long time , The strangest thing is that I haven't been busy lately , Autumn moves are just around the corner , This article only records the process of question brushing , Prepare for future review
One 、 Combinatorial summation
This problem is a typical DFS, Search deeply by selecting and not selecting two states , Because a number can be selected unlimited times , So in recursion , There is no need to add one to the subscript

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 ;
        }
        // No election 
        dfs(candidates,target,item,ans,index+1);
		// choose 
        if(target-candidates[index] >= 0){
    
            item.add(candidates[index]);
            dfs(candidates,target-candidates[index],item,ans,index);
            item.remove(item.size()-1);
        }
    
    }
}

Two 、 Combinatorial summation II
This question is more restrictive than the previous one , Each number can only be used once , And cannot contain duplicate sets
1、 Use each number once ： This only needs to let index++ It can be solved , The current number is selected , You can't choose this number
2、 Cannot contain duplicate sets ： We can arrange the array first , In each layer of the loop, only A number , for example ：1 1 1 2 2 This group of numbers , If the first one is selected in the first layer of loop 1, Then you can't choose the second 1, The next time you choose to meet the conditions, you can only choose 2, Otherwise, it will cause repeated problems

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]){
    // Prevent the same layer from circulating and selecting the same number 
                continue;
            }
            if(target - candidates[i] >= 0){
    
            item.add(candidates[i]);
            dfs(candidates,target-candidates[i],item,ans,i+1);
            item.remove(item.size()-1);
            }
        } 
    }
}