时间轴

2025-11-29

init

题目：

P39 组合总和

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

回溯，注意start,因为可以用重复数字，所以backtrace用i作为下一个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) { //剪枝
				break;
			}
			path.push_back(candidates[i]);
			// 进入下一层
			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;
	}
};