Tag: 回溯

思路

回溯
先把candidate排个序，这样可以在中途直接cut掉后面的loop
为了避免重复结果，需要传入一个startIndex，在这之前的都不能作为candidate

代码

class Solution {
public:
    void combSumSub(vector<int>& candidates, int target, vector<vector<int>>& results, vector<int> currPath, int candStartIndex){
        for(int i=candStartIndex; i<candidates.size(); i++){
            if(target - candidates[i] < 0)
                break; //too big
            if(target == candidates[i]){
                currPath.push_back(candidates[i]);
                results.push_back(currPath);
                continue;
            }
            currPath.push_back(candidates[i]);
            combSumSub(candidates, target - candidates[i], results, currPath, i);
            currPath.erase(currPath.end()-1);
        }
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        vector<vector<int>> result;
        combSumSub(candidates, target, result, vector<int>(), 0);
        return result;
    }
};