leetcode/Combination_Sum2.cpp at master · panzg123/leetcode · 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution
{
public:
    void combinationSumHelper(vector<vector<int>>& result, vector<int>& candidates,
                              int right, int target, vector<int>& partResult)
    {
        int upperBound = upper_bound(candidates.begin(), candidates.begin() + right, target) - candidates.begin() - 1;
        if (upperBound < 0) return;

        for (int i = upperBound; i >= 0; i--)
            {
                int newTarget = target - candidates.at(i);
                partResult.push_back(candidates.at(i));
                if (newTarget == 0)
                    {
                        result.push_back(partResult);
                        partResult.pop_back();

                        // skip duplicate number to prevent duplicate solution
                        while (i > 0 && candidates.at(i) == candidates.at(i - 1))
                            i--;
                        continue;
                    }

                // i+1 is changed to i to only use a number once
                combinationSumHelper(result, candidates, i, newTarget, partResult);
                partResult.pop_back();

                // skip duplicate number to prevent duplicate solution
                while (i > 0 && candidates.at(i) == candidates.at(i - 1))
                    i--;
            }
    }

    vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
    {
        vector<vector<int>> result;
        if (candidates.empty()) return result;

        sort(candidates.begin(), candidates.end());

        vector<int> partResult;
        combinationSumHelper(result, candidates, candidates.size(), target, partResult);
		for (auto& r : result)
            reverse(r.begin(), r.end());
        return result;
    }
};