回溯算法-leetcode#39-組合總和

class Solution {
public:
    vector<vector<int>> all;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    if(candidates.empty()) return all;
    vector<int> one;
    sort(candidates.begin(),candidates.end());
    com(candidates,target,one,0);
    return all;
    }
    void com(vector<int>& num,int target,vector<int> & one,int begin){
        if(target==0) {all.push_back(one); return;}
        for(int i=begin;i<num.size()&&num[i]<=target;i++)
        {
             if(num[i]<=target) 
             {
                 one.push_back(num[i]);
                 com(num,target-num[i],one,i);
             }
             one.pop_back();
        }
    }
};
           

自己寫了一個，發現有重複序列，比如[2,3,6,7]中[2,2,3]和[2,3,2]不能重複出現，是以就是在遞歸的時候，限制下标大于等于剛剛使用過的下标i。當target目标是0時，說明one中序列比對好了，直接加到最終結果all裡面即可。奧對，提前排了個序，減少周遊次數。