这题的主要思路参考 [75. Combination Sum](../75. Combination Sum), 大同小异，涉及的思想，依旧是 DFS。
要额外注意的有两点：
- Each number in C may only be used once in the combination.
- The solution set must not contain duplicate combinations.
对于第一点，我们可以在递归中，给下一个 start 传参为 i+1 来解决。
对于第二点，有两种思路：
- 使用
std::set<vector<int>>来存储返回值，缺点是效率较低。 - 在递归函数中增加条件：
if (i > start && num[i] == num[i-1]) continue;无比轻巧的避过了重复项。
我当然选择了第二种，效率遥遥领先呢。
#include <vector>
#include <set>
using std::vector;
#include <algorithm>
#include <functional>
class Solution {
public:
void dfs(const vector<int> &num, vector<vector<int>> &ret, int target, vector<int> cur, size_t start) {
if (target == 0) { ret.push_back(cur); return; }
for (auto i = start; i < num.size(); ++i)
if (i > start && num[i] == num[i-1]) continue;
else if (num.at(i) <= target) {
cur.push_back(num.at(i));
dfs(num, ret, target - num.at(i), cur, i+1);
cur.pop_back();
} else break;
}
vector<vector<int> > combinationSum2(vector<int> &num, int target) {
vector<vector<int>> ret;
std::sort(num.begin(), num.end());
dfs(num, ret, target, vector<int>{}, 0);
return ret;
}
};