LeetCode - 40. Combination Sum II

Question

题目

解析

这题和 LeetCode - 39 . Combination Sum 不同的地方在于:

• LeetCode - 39 . Combination Sum 数组没有重复的元素，但是你可以使用同一个位置的元素去组成 target ；
• 而此题，数组中可能存在重复的元素，但是你不能使用同一个位置的元素；
• 由于这一题可以使用不同位置上值相同的元素，所以 dfs 得到的结果 res 中可能存在重复的答案，例如第一个示例中，如果不去重，答案会是 [1, 7], [1, 7], [1, 2, 5], [1, 2, 5], [2, 6], [1, 1, 6] ，可以看到有两个重复的答案。所以需要去重。下面给出两种代码实现去重的方式。

① 其实只需要在 LeetCode - 39 . Combination Sum 的基础上加上一行代码，当有连续重复（在排序之后) 的值时，跳过即可，即 while(i+1 < nums.length && nums[i] == nums[i+1]) i++; 。

import java.io.*;
import java.util.*;

class Solution {

    private List<List<Integer>>res;

    //不同点: 不能使用同一个位置上的元素，但是不同位置上可能有相同值的元素，所以-->需要考虑重复答案的问题
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new ArrayList<>();
        if(candidates == null || candidates.length == 0)
            return res;
        Arrays.sort(candidates); //先排序 ,既可以剪枝，由导致相邻相等的元素在一起
        dfs(candidates, target, 0, 0, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, int target, int curSum, int cur, List<Integer>curr){ 
        if(curSum == target){ 
            res.add(new ArrayList<>(curr));
            return;
        }
        for(int i = cur; i < nums.length; i++){ 
            if(curSum + nums[i] > target) 
                break; // 因为排序了，所以这里是 break，不是 continue，剪枝
            curr.add(nums[i]);
            dfs(nums, target, curSum + nums[i], i+1, curr); // notice is i+1             
            curr.remove(curr.size()-1);
            while(i+1 < nums.length && nums[i] == nums[i+1]) i++; //only add this;
        }
    }

    public static void main(String[] args){
        PrintStream out = System.out;
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        out.println(new Solution().
            combinationSum2(candidates, target)
        );
    }
}

② 或者在递归之前判断一下和前面的 nums[i-1] 是不是相同，即: if(i != cur && nums[i] == nums[i-1]) continue;

class Solution {

    private List<List<Integer>>res;

    //不同点: 不能使用同一个位置上的元素，但是不同位置上可能有相同值的元素，所以-->需要考虑重复答案的问题
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        res = new ArrayList<>();
        if(candidates == null || candidates.length == 0)
            return res;
        Arrays.sort(candidates); //先排序 ,既可以剪枝，由导致相邻相等的元素在一起
        dfs(candidates, target, 0, 0, new ArrayList<>());
        return res;
    }

    private void dfs(int[] nums, int target, int curSum, int cur, List<Integer>curr){ 
        if(curSum == target){ 
            res.add(new ArrayList<>(curr));
            return;
        }
        for(int i = cur; i < nums.length; i++){ 
            if(curSum + nums[i] > target) 
                break; 
            if(i != cur && nums[i] == nums[i-1])// judge this 
                continue;
            curr.add(nums[i]);
            dfs(nums, target, curSum + nums[i], i+1, curr); // notice is i+1             
            curr.remove(curr.size()-1);
        }
    }

}