216. 组合总和 III

🟠   🔖  数组 回溯  🔗 力扣 LeetCode

题目

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

• Only numbers 1 through 9 are used.
• Each number is used at most once.

Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7

Output: [[1,2,4]]

Explanation:

1 + 2 + 4 = 7

There are no other valid combinations.

Example 2:

Input: k = 3, n = 9

Output: [[1,2,6],[1,3,5],[2,3,4]]

Explanation:

1 + 2 + 6 = 9

1 + 3 + 5 = 9

2 + 3 + 4 = 9

There are no other valid combinations.

Example 3:

Input: k = 4, n = 1

Output: []

Explanation: There are no valid combinations.

Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.

Constraints:

• 2 <= k <= 9
• 1 <= n <= 60

题目大意

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

• 只使用数字 1 到 9
• 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

解题思路

可以通过回溯算法和递归找到所有满足给定条件的组合：

1. 定义结果数组 res 用于存储符合条件的组合，以及路径数组 track 用于暂时存储当前组合的数字。
2. 使用 backtrack 函数进行递归搜索，其中 start 参数表示搜索的起始数字，保证每个数字最多使用一次。
3. 在递归的过程中，判断当前组合的长度是否等于 k 且组合的和是否等于目标值 n，如果满足条件，则将当前组合加入结果数组。
4. 在递归的过程中，进行剪枝：
   • 如果当前组合的和超过目标值 n，则直接返回，因为后续的数字只会更大，无法满足条件。
   • 如果当前组合的长度超过 k，则直接返回，因为组合中的数字过多。
5. 循环遍历数字 i，将其加入当前组合，并更新组合的和。然后递归调用 backtrack 函数，并在递归完成后将数字 i 弹出组合，同时更新组合的和，以便回溯到上一层。
6. 最终返回结果数组 res。

代码

/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
	let res = [];
	let track = [];
	let sum = 0;

	const backtrack = (start) => {
		// 找到一个满足条件的组合
		if (track.length == k && sum == n) {
			res.push([...track]);
			return;
		}
		// 当前组合的和超过 n ，剪枝
		if (sum > n) {
			return;
		}
		// 当前组合的长度超过 k ，剪枝
		if (track.length > k) {
			return;
		}
		for (let i = start; i <= 9; i++) {
			track.push(i);
			sum += i;
			backtrack(i + 1);
			track.pop();
			sum -= i;
		}
	};
	backtrack(1);
	return res;
};

相关题目

题号	标题	题解	标签	难度
39	组合总和	[✓]	数组 回溯