39. Combination Sum

39. Combination Sumopen in new window

🟠 🔖 数组 回溯 🔗 LeetCodeopen in new window

题目

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 个。

解题思路

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

定义回溯函数： 定义一个回溯函数 backtrack，接收一个起始索引 start 作为参数，表示从候选数组的哪个位置开始考虑，避免重复组合。
回溯过程： 在回溯的过程中，不断选择当前位置的数字，并更新当前组合的和 sum。如果 sum 等于目标值 target，则将当前组合添加到结果集中。
递归调用： 如果 sum 小于 target，则继续在当前位置和之后的位置进行递归。如果 sum 大于 target，说明当前组合不满足条件，需要撤销当前选择，返回上一层继续尝试其他分支。
限制条件： 在递归的过程中，通过判断 sum 是否等于 target 来确保生成的组合是符合要求的。递归时传入 i 作为参数，表示从当前位置开始尝试，以确保可以重复使用当前数字。
返回结果： 最终通过调用 backtrack 函数得到所有符合条件的组合，返回这些组合的数组作为结果。

代码

/**
 * @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;
};

39. Combination Sum

# 39. Combination Sumopen in new window

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

39. Combination Sumopen in new window

题目

题目大意

解题思路

代码

相关题目