Leetcode 40: combined sum II

link

Ideas ： to flash back （ Elements can be duplicated and cannot be checked ）

The combination problem is equivalent to the subset problem ！ Question combination means asking and doing tartget Subset ;
Use extra sum To record the sum of elements ！sum Recorded elements and path The recorded elements are the same , After recursion ends, it is also connected with path Same withdrawal ！

Elements Repeat be ① First Sort ② use i>start && nums[i]==nums[i-1] To screen ！

Be careful ：
When sum Has more than target There's no need to traverse , Save money ！

class Solution {
    
    List<List<Integer>> res=new LinkedList<>();
    LinkedList<Integer> path=new LinkedList<>();
    int sum=0;
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
    
        // If there is repetition, you should sort first  ！
        Arrays.sort(nums);
        dfs(nums,target,0);
        return res;
    }

    void dfs(int[] nums,int target,int start){
    
        // Termination conditions 1 ： Meet the conditions to add to res
        if(sum==target){
    
            res.add(new LinkedList(path));
            return;
        }
        // Termination conditions 2 ： When sum Greater than target direct return, Otherwise, the time limit is exceeded ！
        if(sum>target){
    
            return;
        }
        for(int i=start;i<nums.length;i++){
    
            // choice 
            if(i>start && nums[i]==nums[i-1]){
    
                continue;
            }
            path.add(nums[i]);
            sum+=nums[i];
            //
            dfs(nums,target,i+1);
            // revoke 
            path.removeLast();
            sum-=nums[i];
        }
    }
}