[Leetcode 40] Combination Sum II

作者 Shilei Tian 日期 2016-12-28
[Leetcode 40] Combination Sum II

题目要求

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

Each number in C 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.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,

A solution set is:

[

​ [1, 7],

​ [1, 2, 5],

​ [2, 6],

​ [1, 1, 6]

]

解题思路

这道题与 Combination SumCombination Sum II 不同的地方在于,所给集合元素有重复的。这就会导致,直接套用之前的代码,就会出现两次 [1, 7] 这种情况。究其原因,还是因为当 1 作为栈底元素时,要能区分的了是第一次的 1 还是第二次的 1。上面这句话是什么意思呢?我们考虑当第一个 1 在栈底时,如果我们已经将第二个 1 的情况考虑完了,也就是说,现在的集合看起来就变成了 [1, 2, 5, 6, 7, 10],那么和直接第二个 1 是栈底的情况是重复的。那么什么情况下会出现第二个 1 是栈底的情况呢?那么就是,我们已经考虑完了第一个 1 为栈底的情况,此时,那个为了确保顺序的变量(我们记为 start)仍然是 0

为了防止出现重复的集合,我们需要处理上述的情况。通过的技巧,就是当我们已经搜索完(那些重复元素的)第一个元素了,我们这时会搜索下一个元素。但此时,标记我们当前要搜索元素的那个变量与 start 是不相同的,准确的说,是要大于 start 的,因此,我们只需要判断,如果当前元素和之前刚搜索完的元素相等时,我们就可以跳过这种情况。这样,我们既可以保证这些重复元素能够有那种同时被选上的情况,也可以保证出现重复选择集合的情况。

具体的代码如下:

class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ret;
vector<int> res;
sort(candidates.begin(), candidates.end());
sum(candidates, target, 0, res, ret);
return ret;
}
private:
void sum(const vector<int>& candidates, int target, const int start, vector<int>& res, vector<vector<int>>& ret) {
if (target < 0) {
return;
} else if (target == 0) {
ret.push_back(res);
return;
}
for (int i = start; i < candidates.size(); ++i) {
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
res.push_back(candidates[i]);
sum(candidates, target - candidates[i], i + 1, res, ret);
res.pop_back();
}
}
};