LeetCode.40. 组合总和 II

LeetCode.40. 组合总和 II

难度:medium

 本题可以和  LeetCode.39. 组合总和 对比分析，主要区别有两个：

• 39题每个元素是可以重复取用的，所以startIndex = i；而本题目不能重复取用，所以 startIndex = i + 1；
• 本题的集合为有重复元素的集合，但题目要求不能有重复组合，所以我们需要used数组来去重

要去重的是“同一树层上的使用过”，如果判断同一树层上元素（相同的元素）是否使用过了呢。

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作

在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：

• used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
• used[i - 1] == false，说明同一树层candidates[i - 1]使用过

Java:

class Solution {
    List> ans = new ArrayList>();
    List path = new ArrayList();
    int sum = 0;
 
    public List> combinationSum2(int[] candidates, int target) {
        // 需要使用used数组，所以需要排序
        Arrays.sort(candidates);
 
        boolean[] used = new boolean[candidates.length];
        backTracking(candidates, target, used, 0);
        return ans;
    }
 
    public void backTracking(int[] candidates, int target, boolean[] used, int startIndex) {
        if (sum == target) {
            ans.add(new ArrayList<>(path));
            return;
        }
 
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
 
            sum += candidates[i];
            path.add(candidates[i]);
            used[i] = true;
            backTracking(candidates, target, used, i + 1);
            sum -= candidates[i];
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}