https://leetcode.cn/problems/combination-sum/description/

<aside> 💡

本题中一个元素可以被重复选取，所以与前几题有些不同：

• 每次递归传入的是 i 而非 i+1 （使得下一层递归仍然能使用索引i处的元素）

求总和相关题目的小技巧：在传入输入数组前先对该数组进行排序

</aside>

vector<int> cur;
vector<vector<int>> ans;

void backtracking(int pos, int sum, vector<int>& candidates, int target) {
    if (sum == target) {
        ans.push_back(cur);
        return;
    }

    for (int i = pos; i < candidates.size(); ++i) {
        // candidates为已排序，可以进行如下剪枝
        if (sum + candidates[i] > target) {
            return;
        }
        cur.push_back(candidates[i]);
        backtracking(i, sum + candidates[i], candidates, target);
        cur.pop_back();
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    std::sort(candidates.begin(), candidates.end());
    backtracking(0, 0, candidates, target);
    return ans;
}