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] ]
又是求和问题，博主的使用递归的方法，虽然给出正确结果，但是存在效率的问题：
class Solution {
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> accumulate;
std::sort(candidates.begin(), candidates.end());
int index = 0;
for (int i = 0; i < candidates.size(); i++){
if (i && candidates.at(i - 1) == candidates.at(i)) continue;
m_temp.clear();
if (candidates.at(i) < target){
m_temp.push_back(candidates.at(i));
accumulate.assign(candidates.begin() + i + 1, candidates.end());
combinationSum2Iter(accumulate, target - candidates.at(i));
m_temp.pop_back();
}
else if (candidates.at(i) == target){
m_temp.push_back(candidates.at(i));
result.push_back(m_temp);
m_temp.pop_back();
break;
}
else{
break;
}
}
return result;
}
protected:
vector<int> m_temp;
vector<vector<int>> result;
void combinationSum2Iter(vector<int>& candidate, int target){
vector<int> accumulate;
for (int i = 0; i < candidate.size(); i++){
if(i && candidate.at(i-1) == candidate.at(i)) continue;
if (candidate.at(i) < target){
m_temp.push_back(candidate.at(i));
accumulate.assign(candidate.begin() + i + 1, candidate.end());
combinationSum2Iter(accumulate, target - candidate.at(i));
m_temp.pop_back();
}
else if (candidate.at(i) == target){
m_temp.push_back(candidate.at(i));
result.push_back(m_temp);
m_temp.pop_back();
break;
}
else{
break;
}
}
}
};
代码比较长，下面总结一下递归法处理的思路：
1.先将数列进行排序，然后按照定和问题的思路来解决；
2.判断最小的数字是不是小于target_sum，如果小于target_sum，则这个数value入栈，右边的数字中需要和为target_sum – value，这样就编程了一个定和的递归问题。每次从中取出一个数，如果可以使和 小于 target，则继续取，如果 等于 target 则保存结果，如果大于target，则终止；
note：每次入栈，都对应一次出栈，递归法思路不好理，这一点一定要理解并且要作为基本常识。
3.由于遇到重复值需要跳过，则有下面这段经典代码：
for (int i = 0; i < candidate.size(); i++){
if(i && candidate.at(i-1) == candidate.at(i)) continue;
这段代码怎样理解呢，我们假设输入序列是[1 1 1 3 1 3 6]，target是6，我们会担心得不到[1 1 1 3]这样的结果，事实上，这种担心是不必要的。第一次进栈的是1，后面的序列为[1 1 1 3 3 6]，第二次进栈的是1，剩下的是[1 1 3 3 6] …… ，得到[1 1 1 3]后，事实上我们已经将第一个数字为1的情况都考察过了。当我们再次选取第一个数字时，如果我们不跳过，也就是说假设我们没有if这句代码，我们会得到三个 [1 1 1 3] 这种重复的答案，这其中还有玄机，遍历第一个数字时的重复会增加一个，遍历第二个数字带来的重复也会增加一个，遍历第三个数字时的重复也会增加一个，最先发生的是最后一种情况，那么我们就能够理解代码中的这两处的if跳过了。
OK，See You Next Chapter!