代码随想录：组合总和

回溯的本质就是多层for循环嵌套，用于解决不知道有多少层for循环的情况，适当剪枝其实也是for循环里增加限制条件

class Solution {
public:
    vector<int> sum;
    vector<vector<int>> res;
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        bk(candidates, target,0);
        return res;
    }
    void bk(vector<int> candidates, int target,int start) {
        if (s(sum) == target) {
            res.push_back(sum);
            return;
        }

        if (s(sum) > target) {
            return;
        }

        for (int i = start;i<candidates.size();i++) {
            sum.push_back(candidates[i]);
            bk(candidates, target,i);
            sum.pop_back();
        }
    }

    int s(vector<int> nums) {
        int res = 0;
        for (int n : nums) {
            res += n;
        }
        return res;
    }
};