39. 组合总和

🟠   🔖  数组 回溯  🔗 力扣 LeetCode

题目

Given an array of distinct integers candidates and a target integer target, return _a list of all unique combinations of _candidateswhere the chosen numbers sum totarget . You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

The test cases are generated such that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3],[7]]

Explanation:

2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.

7 is a candidate, and 7 = 7.

These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8

Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1

Output: []

Constraints:

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• All elements of candidates are distinct.
• 1 <= target <= 40

题目大意

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

解题思路

这个问题使用回溯法来解决。回溯法是一种通过不断尝试生成问题的所有解的算法，如果解不符合要求，就撤销上一步甚至上几步的计算，再通过其他可能的分支寻找正确的解。具体步骤如下：

1. 定义回溯函数： 定义一个回溯函数 backtrack，接收一个起始索引 start 作为参数，表示从候选数组的哪个位置开始考虑，避免重复组合。

2. 回溯过程： 在回溯的过程中，不断选择当前位置的数字，并更新当前组合的和 sum。如果 sum 等于目标值 target，则将当前组合添加到结果集中。

3. 递归调用： 如果 sum 小于 target，则继续在当前位置和之后的位置进行递归。如果 sum 大于 target，说明当前组合不满足条件，需要撤销当前选择，返回上一层继续尝试其他分支。

4. 限制条件： 在递归的过程中，通过判断 sum 是否等于 target 来确保生成的组合是符合要求的。递归时传入 i 作为参数，表示从当前位置开始尝试，以确保可以重复使用当前数字。

5. 返回结果： 最终通过调用 backtrack 函数得到所有符合条件的组合，返回这些组合的数组作为结果。

复杂度分析

• 时间复杂度：O(n^t)，n 为 candidates 长度，t = target / 最小候选数，主要由递归树的深度和每层递归中循环次数决定。
  • 递归树的每一层代表从数组 candidates 中选择一个数字加入到组合中的过程。每个数字都可以重复使用，因此递归树的深度最大为 target / 最小候选数。
  • 在最坏情况下，递归树的每个节点都要进行 n 次循环操作来选择候选数，因此递归树的节点总数最多为 n^(target / 最小候选数)。
• 空间复杂度：O(t)，t = target / 最小候选数，主要由递归深度决定，递归树的深度可能达到 target / 最小候选数。

代码

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function (candidates, target) {
	const len = candidates.length;
	let res = [];
	let track = [];
	let sum = 0;

	const backtrack = (start) => {
		// 满足条件
		if (sum == target) {
			res.push([...track]);
			return;
		}
		// 剪枝
		if (sum > target) {
			return;
		}
		for (let i = start; i < len; i++) {
			track.push(candidates[i]);
			sum += candidates[i];

			// 注意这里传入的参数是 i 而不是 i + 1，表示可以重复使用当前的数字
			backtrack(i);

			track.pop();
			sum -= candidates[i];
		}
	};
	backtrack(0);
	return res;
};

相关题目

题号	标题	题解	标签	难度
17	电话号码的字母组合	[✓]	哈希表 字符串 回溯
40	组合总和 II	[✓]	数组 回溯
77	组合	[✓]	回溯
216	组合总和 III	[✓]	数组 回溯
254	因子的组合 🔒		回溯
377	组合总和 Ⅳ		数组 动态规划
3183	达到总和的方法数量 🔒		数组 动态规划