#leetcode 40. Задача Combination Sum II через backtracking

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
    sort(candidates.begin(), candidates.end()); // сортируем массив

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

    dfs(candidates, target, ans, cur, 0, 0);

    return ans;
}

// TODO функция должна принимать ОТСОРТИРОВАННЫЙ МАССИВ candidates
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int curSum, int start) {
    if (curSum == target) {
        ans.push_back(cur);
        return;
    }

    if (curSum > target) {
        return;
    }

    for (int j = start; j < candidates.size(); ++j) {

        if (j > start && candidates[j - 1] == candidates[j]) {
            continue;
        }

        cur.push_back(candidates[j]);
        dfs(candidates, target, ans, cur, curSum + candidates[j], j + 1);
        cur.pop_back();
    }

    return;
}