@Leetcode
本题与Leetcode216 组合总和III以及LeetCode77 Combinations的区别是，集合里面的元素可以重复使用，故递归没有层数限制，只要选取元素总和为target，即可返回。而另外两个知道得递归k层，因为要取k个元素的集合。

回溯三步曲

• 递归函数参数

void generateSum(vector<int>& candidates, int target, int startIndex, int &sum, vector<int> &p)

• 终止条件

if(sum == target){
           res.push_back(p);
           return;
       }
       

• 单层搜索过程

for(int i = startIndex; i < candidates.size(); i++){
            if(sum + candidates[i] <= target){
                p.push_back(candidates[i]);
                sum = sum + candidates[i];

                generateSum(candidates, target,  i, sum, p);//不用i+1了，表示可以取重复的数（与combination的区别之处）

                sum = sum - candidates[i];
                p.pop_back();

            }
            
            
        }

全部代码:

class Solution {
private:
    int sum = 0;
    vector<vector<int>> res;
    void generateSum(vector<int>& candidates, int target, int start, int &sum, vector<int> &p){
        if(sum == target){
            res.push_back(p);
            //cout<<p[0]<<":"<<endl;
            //for(int i = 0; i < p.size(); i++)
                //cout<<p[i];
            //p[0] = true;
            //cout<<endl;
            //cout<<"return1"<<endl;
            return;
        }
        

        for(int i = start; i < candidates.size() && sum + candidates[i] <= target; i++){
            
            p.push_back(candidates[i]);
            sum = sum + candidates[i];

            generateSum(candidates, target,  i, sum, p);//不用i+1了，表示可以取重复的数（与combination的区别之处）

            sum = sum - candidates[i];
            p.pop_back();

            
            
            
        }

        return;
    }
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        res.clear();
        vector<int> p;

        sort(candidates.begin(), candidates.end());

        generateSum(candidates, target, 0, sum, p);

        return res;
    }
};