CPP/combinationSum2.cpp at master · anishmo99/CPP · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
public:
    void backtrack(vector<vector<int>> &ans, vector<int> &nums, vector<int> temp, int remain, int index)
    {
        if (remain < 0)
            return;
        else if (remain == 0)
        {
            ans.emplace_back(temp);
            return;
        }
        else
        {
            for (int i = index; i < nums.size(); i++)
            {
                temp.push_back(nums[i]);
                backtrack(ans, nums, temp, remain - nums[i], i + 1);
                temp.pop_back();
                while (i + 1 < nums.size() and nums[i] == nums[i + 1])
                    i++;
            }
        }
    }

    vector<vector<int>> combinationSum2(vector<int> &nums, int target)
    {
        sort(nums.begin(), nums.end());
        vector<vector<int>> ans;
        backtrack(ans, nums, vector<int>(), target, 0);
        return ans;
    }
};