Cover image for Interview Classic 150 Questions P39 Combination Sum

Interview Classic 150 Questions P39 Combination Sum

(Updated: )
algorithm
, , ,
Timeline

Timeline

2025-11-29

init

Title:

P39 Combination Sum

https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-interview-150

Backtracking, note start, because duplicate numbers can be used, so backtrace uses i as the next start.

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
#include <vector>
#include <algorithm>
using std::vector;

class Solution {
    private:
	vector<vector<int> > res;
	void backtrace(vector<int> &path, vector<int> &candidates, int start, int target)
	{
		if (target == 0) {
			res.push_back(path);
			return;
		} else if (target < 0) {
			return;
		}

		for (int i = start; i < candidates.size(); i++) {
			if (candidates[i] > target) { //Pruning
				break;
			}
			path.push_back(candidates[i]);
			// Enter next level
			backtrace(path, candidates, i, target - candidates[i]);
			path.pop_back();
		}
	}

    public:
	vector<vector<int> > combinationSum(vector<int> &candidates, int target)
	{
		vector<int> path;
		std::sort(candidates.begin(), candidates.end());
		backtrace(path, candidates, 0, target);
		return res;
	}
};

leetcode hot 100 rewrite

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
#include <vector>

using std::vector;

class Solution {
    private:
        void __combinationSum(vector<int> &candidates, int target, vector<vector<int> > &res,
                              vector<int> &curr, int curr_sum, int pos)
        {
                if (curr_sum == target) {
                        res.push_back(curr);
                        return;
                } else if (curr_sum > target) {
                        return;
                }

                int i, n = candidates.size();
                for (i = pos; i < n; i++) {
                        curr.push_back(candidates[i]);
                        curr_sum += candidates[i];

                        __combinationSum(candidates, target, res, curr, curr_sum, i);

                        curr_sum -= candidates[i];
                        curr.pop_back();
                }
        }

    public:
        vector<vector<int> > combinationSum(vector<int> &candidates, int target)
        {
                vector<vector<int> > res;
                vector<int> curr;
                __combinationSum(candidates, target, res, curr, 0, 0);

                return res;
        }
};