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!