39. 組合總和 - 力扣（LeetCode）?

class Solution {
private:vector<vector<int>>result;vector<int>path;void backtracking(vector<int>& candidates, int target,int sum,int startIndex){if(sum>target){return;}if(sum==target){result.push_back(path);return;}for(int i=startIndex;i<candidates.size();i++){path.push_back(candidates[i]);sum+=candidates[i];backtracking(candidates,target,sum,i);sum-=candidates[i];path.pop_back();}}
public:vector<vector<int>> combinationSum(vector<int>& candidates, int target) {backtracking(candidates,target,0,0);return result;}
};

這道題的搜索過程可以構造成樹形結構，與其他組合問題不同的是可以再次搜索自己本身，最后找到路徑和等于目標值。?

終止條件：路徑和如果大于目標值，則返回到上一次遞歸；如果路徑和與目標值相等，則將路徑數組的值push進result數組中。

單層遞歸邏輯：定義一個數startIndex來統計遍歷到數組的哪一個數，遍歷這個數本身到最后的所有數，將遍歷的數push入path數組中，定義sum統計遍歷到現在的路徑和，再向下進行遞歸，傳入的startIndex值是i,因為搜索的值可以是自己本身。為了返回到上一層再進行新遞歸，所以要進行回溯算法，sum值減去加入的值，path數組pop出剛剛push進的值。