LeetCode/39.cpp at master · changqing18/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
#include <algorithm>
#include <stdio.h>
#include <vector>
using namespace std;

vector<vector<int>> ans;
int length;

void help(vector<int> &candidates, int cur[], int target, int loc, int len);

vector<vector<int>> combinationSum(vector<int> &candidates, int target)
{
    length = candidates.size();
    sort(candidates.begin(), candidates.begin() + length);
    int cur[target / candidates[0]];

    for (int i = 0; i < length; i++)
    {
        if (candidates[i] <= target)
        {
            cur[0] = candidates[i];
            help(candidates, cur, target - candidates[i], i, 1);
        }
        else
            break;
    }
    return ans;
}

void help(vector<int> &candidates, int cur[], int target, int loc, int len)
{
    if (target == 0)
    {
        vector<int> one(cur, cur + len);
        ans.push_back(one);
        return;
    }
    for (int i = loc; i < length; i++)
    {
        if (candidates[i] <= target)
        {
            cur[len] = candidates[i];
            help(candidates, cur, target - candidates[i], i, len + 1);
        }
        else
            break;
    }
}