class Solution {

public:

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        vector<vector<int>> res;

        if(candidates.size() == ) return res;

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

        vector<int> tmp;

        combinationSum(candidates, target, res, tmp, );

        return res;

    }

    void combinationSum(vector<int>& candidates, int target, vector<vector<int>>& res, vector<int>& tmp, int begin){

        if(!target){

            res.push_back(tmp); //如果target在等于0的时候添加到res，只有target等于0时进入

            return;

        }

        for(int i = begin; i != candidates.size() && target - candidates[i] >= ; ++i){

            tmp.push_back(candidates[i]);  //加入到tmp中

            combinationSum(candidates, target - candidates[i], res, tmp, i);  //遍历下一个元素，进入递归

            tmp.pop_back();  //跳过上次遍历，开始输入后续元素，直到tmp为空，向后移位继续遍历

        }

    }

};

class Solution {

public:

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {

    sort(candidates.begin(), candidates.end()); //先对数组进行排序

    vector< vector< vector<int> > > DP(target + , vector<vector<int>>()); //初始化DP数组，长度为target + 1

    DP[].push_back(vector<int>()); // 初始化DP[0]为[[]]

    for (auto& score : candidates)  // 开始遍历给定的数组

        for (int j = score; j <= target; j++){ //从DP的j~target遍历

            auto tmp = DP[j - score];  //找到tmp位置使得tmp + score = j

            if (tmp.size() > ) {

                for (auto& s : tmp)

                    s.push_back(score); //将score添加到tmp的每一个元组里

                DP[j].insert(DP[j].end(), tmp.begin(), tmp.end()); //在DP[j]的末尾加入tmp

            }

        }

    return DP[target];

}

};