leetcode/0039.combination_sum.cpp at main · 1ambd4/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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <algorithm>
#include <iostream>
#include <vector>

#include "leetcode.h"

using std::vector;

vector<vector<int>> combinatioin_sum(vector<int>& candidates, int t)
{
    vector<vector<int>> res;
    vector<int> path;
    int n = candidates.size();

    auto backtracking = [&candidates, &res, &path, n, t](auto&& self, int s, int k) -> void {
        if (s > t) return ;
        if (s == t) {
            res.push_back(path);
            return ;
        }

        // 这题元素可以重复，那么有两种思路
        // 一种是每次都是 [0, n-1] 的遍历所有的元素
        // 另一种思路则是下一次仍旧从当前元素开始遍历
        // 使用前者的一个缺点是可能出现重复的 path，比如 [2, 2, 3] 和 [2, 3, 2]
        // 那么就需要排序再去重，明显麻烦很多
        // 而方法二，因为不可能出现相同的路径
        // 那么自然不可能出现重复的结果
        for (int i = k; i < n; ++i) {
            path.push_back(candidates[i]);
            s += candidates[i];
            self(self, s, i);
            s -= candidates[i];
            path.pop_back();
        }
    };

    backtracking(backtracking, 0, 0);

    return res;
}

vector<vector<int>> _combinatioin_sum(vector<int>& candidates, int t)
{
    vector<vector<int>> res;
    vector<int> path;
    int n = candidates.size();

    // 用 path 的话，如何去重呢？
    auto backtracking = [&candidates, &res, &path, n, t](auto&& self, int s) -> void {
        if (s > t) return ;
        if (s == t) {
            // 不能直接修改原来的数组
            // std::sort(path.begin(), path.end());

            // 排序后去重
            vector<int> temp(path.begin(), path.end());
            std::sort(temp.begin(), temp.end());
            if (std::find(res.begin(), res.end(), temp) == res.end()) {
                res.push_back(temp);
            }
            return ;
        }

        for (int i = 0; i < n; ++i) {
            path.push_back(candidates[i]);
            s += candidates[i];
            self(self, s);
            s -= candidates[i];
            path.pop_back();
        }
    };

    backtracking(backtracking, 0);

    return res;
}

int main () {
#ifdef LOCAL
    freopen("0039.in", "r", stdin);
#endif
    int n = 0, t = 0;
    while (std::cin >> n >> t) {
        vector<int> nums(n, 0);
        for (int i = 0; i < n; ++i) {
            std::cin >> nums[i];
        }
        vector<vector<int>> res = combinatioin_sum(nums, t);
        std::cout << res << std::endl;
    }

    return 0;
}