LeetCode 40. Combination Sum II

[Woodyiiiiiii]

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates may only be used once in the combination.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
  [1,2,2],
  [5]
]

---

这道题跟Combination Sum是同一个思路：DFS+回溯。但因为题目要求不能有重复的集合，我们要做一些处理，排除出现的重复的情况。

首先第一种方法是排序+判断包含：

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Stack<Integer> tmp = new Stack<>();
        Arrays.sort(candidates);
        dfs(res, tmp, candidates, target, 0, 0);
        return res;
    }
    public void dfs(List<List<Integer>> res, Stack<Integer> tmp,
                    int[] candidates, int target, int level, int sum) {
        if (sum > target) return;
        if (sum == target) {
            if (!res.contains(tmp))
                res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = level; i < candidates.length; ++i) {
            sum += candidates[i];
            tmp.push(candidates[i]);
            dfs(res, tmp, candidates, target, i + 1, sum);
            sum -= candidates[i];
            tmp.pop();
        }
    }
}

因为排好序后两个重复List所包含的元素顺序肯定是一样的，而且List的contains方法底层判断逻辑是(o==null ? e==null : o.equals(e))，用equals方法判断，所以可以去除重复的情况。

第二种方法是：if (i > level && candidates[i] == candidates[i - 1]) continue;如果当前元素等于它先前的元素，那么它深度遍历的集合就跟前一个元素是一样的，所以跳过这种情况。为什么是i > level而不是i > 0？因为前者代表的是每个位置遍历的第二个元素起。

class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Stack<Integer> tmp = new Stack<>();
        Arrays.sort(candidates);
        dfs(res, tmp, candidates, target, 0, 0);
        return res;
    }
    public void dfs(List<List<Integer>> res, Stack<Integer> tmp,
                    int[] candidates, int target, int level, int sum) {
        if (sum > target) return;
        if (sum == target) {
            res.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = level; i < candidates.length; ++i) {
            if (i > level && candidates[i] == candidates[i - 1]) continue;
            sum += candidates[i];
            tmp.push(candidates[i]);
            dfs(res, tmp, candidates, target, i + 1, sum);
            sum -= candidates[i];
            tmp.pop();
        }
    }
}

两种方法都要用到排序方法，这是判断List集合是否重复的首要条件。

---

相似题目：

• 39. Combination Sum

参考资料：

• https://leetcode.com/problems/combination-sum-ii/
• [LeetCode] 40. Combination Sum II grandyang/leetcode#40