LeetCode #40：Combination Sum II(组合总和II)

题目描述

本题为 LeetCode #39 的变体，只要在其基础上稍作修改即可。

class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        n = candidates.size();
        temp_sum = 0;
        this->target = target;
        sort(candidates.begin(), candidates.end()); // 修改处1：先要对candidates进行排序
        dfs(candidates, 0);
        return res;
    }

    vector<vector<int>> res;
    vector<int> temp;
    int temp_sum;
    int n;
    int target;

    void dfs(vector<int>& candidates, int j) {
        if(temp_sum > target) { 
            return;
        } else if(temp_sum == target) {
            res.push_back(temp);
            return;
        }

        for(int i = j; i < n; i ++) {
            if(i > j && candidates[i] == candidates[i - 1]) // 修改处2：对重复的组合进行剪枝
                continue;
            temp.push_back(candidates[i]);
            temp_sum += candidates[i];
            dfs(candidates, i + 1);
            temp_sum -= temp.back();
            temp.pop_back();
        }
    }
};

首先我们对 candidates 数组进行排序，便于进行剪枝；随后在 dfs 函数的 for 循环部分进行剪枝，即第 27 行的 if 语句。

为什么 27 行这么写就能避免重复呢？因为if 语句中的条件之一：candidates[i] == candidates[i - 1] 保证了递归运行的过程中，同一递归层级不出现相同的元素（判定当前元素是否和之前元素相同），即下图的情况不会发生。

但是如果只写 candidates[i] == candidates[i - 1]，那么下图这种情况也被剪掉了（当第二个 5 出现的时候，他就和前一个 5 相同了）。然而这种情况也是需要继续搜索下去的，根据题意，不同递归层级是可以出现重复元素的。

那么如何保留这种情况呢？这时就需要加上 i > j 的条件。for 循环中，所有被遍历到的数都是属于同一层级的。我们要让一个层级中， 出现且仅出现一个 5，那么就放过第一个出现的 5，但不放过后面重复出现的 5。 第一个出现的 5 特点是 i == j，那么后面重复出现的 5 必然就满足 i > j。

本题去重的思想可同时用在 #47 与 #90 上。