人森很精彩，所以要把所有事情都記起來=ˇ=

給一個整數陣列，裡面都是正數且沒有重複的數值，另外還會給一個目標值，找出所有可以組成目標值的組合

例如：

Input: candidates = [2,3,6,7], target = 7,

A solution set is:

[ [7], [2,2,3] ]

Sol：

基本上最直觀的就是一個一個全部找出來，思路大概是這樣

比如說以上面的例子來看：

從2開始

2 < 7 -> 2+2=4 < 7 -> 2+2+2=6 < 7 -> 2+2+2+2=8  > 7，回到上一步 -> 2+2+3=7 = 7，是其中一個解，回到上一步

2+2+6 > 7，回到上一步 -> 2+2+7 > 7，再往前回到上一步 

3 -> 3+3 = 6 < 7 -> 3+3+3 > 7，回到上一步->.... 

6 -> 6+6 = 12 > 7 ->....

7 -> 等於7，是其中一個解

基本上是這樣，如果數列是排好序的話，這樣就可以全部解完了

上面是用加法來做，實際上也可以用減法，是一樣的意思

以下是用減法的程式碼：

class Solution {
public:
    vector<int> m_candidates;
    vector<vector<int>> m_viRet;
    
    void generateSol(int target, int index, vector<int>& viSol)
    {
        if (target == 0)
        {
            m_viRet.push_back(viSol);
        }
        else
        {   
            for (int i = index; i < m_candidates.size() && target >= m_candidates[i]; ++i)
            {
                viSol.push_back(m_candidates[i]);
                generateSol(target - m_candidates[i], i, viSol);
                viSol.pop_back();
            }
        }
    }
    
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        m_candidates = candidates;
        
        vector<int> viSol;
        
        generateSol(target, 0, viSol);
        
        return m_viRet;
    }
};

基本上也是用遞迴的方式去一個一個數字找，這種技巧好像叫做Backtracking吧

index就是表示現在找到第幾個數值了

這種技巧可以套用到很多題目， 可以好好參考一下

那麼這題就這樣了=ˇ=