【LeetCode】Combination Sum

给定一组候选正整数的集合Set（没有重复元素）和一个目标正整数 target，找到 Set 中所有的数字组合（可以不限次数地选择同样的数字），使其和 = target。结果集中不能有重复。

e.g. 给定候选正数集 [2, 3, 6, 7] 和target = 7，返回结果集

[
[7],
[2, 2, 3]
]

我的想法是用递归实现，但结果集去重我想了两种低效的方法。

第一种：

 1 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 2     vector<vector<int>> result;
 3     vector<int> item;
 4     addItem(result, candidates, item, target);
 5     sort(result.begin(), result.end());
 6     result.erase(unique(result.begin(), result.end()), result.end());
 7     return result;
 8 }
 9     
10 void addItem(vector<vector<int>>& result, vector<int>& candidates, vector<int> item, int target) {
11     if (target == 0) {
12         sort(item.begin(), item.end());
13         result.push_back(item);
14         return;
15     }
16     for (int i = 0; i < candidates.size(); i++) {
17         if (candidates[i] <= target) {
18             item.push_back(candidates[i]);
19             addItem(result, candidates, item, target - candidates[i]);
20             item.pop_back();
21         }
22     }
23     return;
24 }

unique 函数的作用是“删除” vector 中所有相邻的重复元素，只留一个。

由于 unique 只是去除相邻的重复元素，因此应首先对 vector 进行排序，保证重复元素在相邻的位置。

注意，unique 并不是把重复的元素删除，而是全部放倒 vector 后面（vector 长度没变，顺序改变）。

其本身会返回一个迭代器，返回的是去重后的尾地址，也即指向第一个重复元素。

例如对于 vector {1, 1, 2, 2, 3}，执行 unique 函数后，vector 变成了 {1, 2, 3, 1, 2}，并且函数的返回值为 3。

因此对 vector 去重可使用这种方法：

sort(v.begin(),v.end());
v.erase(unique(v.begin(), v.end()), v.end());

第二种：

 1 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 2     vector<vector<int>> result;
 3     vector<int> item;
 4     addItem(result, candidates, item, target);
 5     return result;
 6 }
 7     
 8 void addItem(vector<vector<int>>& result, vector<int>& candidates, vector<int> item, int target) {
 9     if (target == 0) {
10         sort(item.begin(), item.end());
11         if (find(result.begin(), result.end(), item) == result.end())
12             result.push_back(item);
13         return;
14     }
15     for (int i = 0; i < candidates.size(); i++) {
16         if (candidates[i] <= target) {
17             item.push_back(candidates[i]);
18             addItem(result, candidates, item, target - candidates[i]);
19             item.pop_back();
20         }
21     }
22     return;
23 }

使用 find 函数，如果 find(v.begin(), v.end(), val) 返回的迭代器到容器尾 v.end()，则说明 v 内不存在 val。

答案在递归函数中增加了 begin 参数，并开始就对 candidates 进行排序，这样添加进结果集的 item 就不会有重复的。

 1 vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
 2     vector<vector<int>> result;
 3     vector<int> item;
 4     sort(candidates.begin(), candidates.end());
 5     addItem(result, candidates, item, target, 0);
 6     return result;
 7 }
 8     
 9 void addItem(vector<vector<int>>& result, vector<int>& candidates, vector<int> item, int target, int begin) {
10     if (target == 0) {
11         result.push_back(item);
12         return;
13     }
14     for (int i = begin; i < candidates.size() && candidates[i] <= target; i++) {
15         item.push_back(candidates[i]);
16         addItem(result, candidates, item, target - candidates[i], i);
17         item.pop_back();
18     }
19     return;
20 }

改变条件，candidates 存在重复元素，而数字组合不能不限次数取同样的数字，只能有多少取多少。结果集同样不能有重复。

e.g. 给定候选集合为 [10, 1, 2, 7, 6, 1, 5] 和 target = 8，返回结果集

[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6] （1 在 candidates 中有 2 个就可以用 2 次）
]

 1 vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
 2     vector<vector<int>> result;
 3     vector<int> item;
 4     sort(candidates.begin(), candidates.end());
 5     addItem(result, candidates, item, target, 0);
 6     return result;
 7 }
 8     
 9 void addItem(vector<vector<int>>& result, vector<int>& candidates, vector<int> item, int target, int begin) {
10     if (target == 0) {
11         result.push_back(item);
12         return;
13     }
14     for (int i = begin; i < candidates.size() && candidates[i] <= target; i++) {
15         while (i > begin && candidates[i] == candidates[i - 1]) i++;
16         item.push_back(candidates[i]);
17         addItem(result, candidates, item, target - candidates[i], i + 1);
18         item.pop_back();
19     }
20     return;
21 }

用 while (i > begin && candidates[i] == candidates[i - 1]) i++; 和 addItem(result, candidates, item, target - candidates[i], i + 1); 控制重复！