class Solution {
public:
    vector<vector<int>> ans;//记录所有的答案
    vector<int> path;//满足条件的方案

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
         dfs(candidates, 0, target);//从第一个数开始，从前往后dfs一遍
         return ans;//返回答案即可   
    }
    //dfs暴搜一遍，传入数组，当前枚举到第几个数了，需要凑的值
    void dfs(vector<int>& candidates, int u, int target) {
        //每次的target都会减去前一个数，所以当target减到0说明已经找到了一组解
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        //如果枚举完了所有的数还是没有凑出target，说明无解，直接return
        if (u == candidates.size()) return;
        //枚举一下当前的数可以选几个,可以选0个，或者选i个总和不超过target的个数
        for (int i = 0; i * candidates[u] <= target; i++) {
            //第一次选了0个，也就是什么都没选，所以直接dfs下一个
            dfs(candidates, u + 1, target - i *candidates[u]);
            path.push_back(candidates[u]);//把选的元素加到答案中
        }
        //最后再恢复现场即可
        for (int i = 0; i * candidates[u] <= target; i++) {
            path.pop_back();
        }
    }
};