LeetCode 40：组合总和 II

链接

思路：回溯（元素可重不可复选）

组合问题和子集问题等价！问组合也就是问和为tartget的子集；
使用额外的sum来记录元素的和！sum记录的元素和path记录的元素相同，在递归到头后也和path一样撤回！

元素有重复则① 先排序 ②用 i>start && nums[i]==nums[i-1] 来筛选！

注意：
当sum已经超过target 就不需要遍历了， 节省开销！

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) {
    
        //有重复要先排序 ！
        Arrays.sort(nums);
        dfs(nums,target,0);
        return res;
    }

    void dfs(int[] nums,int target,int start){
    
        //终止条件1 ：满足条件添加到res
        if(sum==target){
    
            res.add(new LinkedList(path));
            return;
        }
        //终止条件2 ：当sum大于target直接return，不然超出时间限制！
        if(sum>target){
    
            return;
        }
        for(int i=start;i<nums.length;i++){
    
            //选择
            if(i>start && nums[i]==nums[i-1]){
    
                continue;
            }
            path.add(nums[i]);
            sum+=nums[i];
            //
            dfs(nums,target,i+1);
            //撤销
            path.removeLast();
            sum-=nums[i];
        }
    }
}