class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
}
};
216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。
示例 1:
输入: k = 3, n = 7 输出: [[1,2,4]] 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。
示例 2:
输入: k = 3, n = 9 输出: [[1,2,6], [1,3,5], [2,3,4]] 解释: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 没有其他符合的组合了。
示例 3:
输入: k = 4, n = 1 输出: [] 解释: 不存在有效的组合。 在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。
提示:
2 <= k <= 91 <= n <= 60相似题目
原站题解
cpp 解法, 执行用时: 4 ms, 内存消耗: 8 MB, 提交时间: 2024-04-21 13:44:11
class Solution {
public:
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> ans;
vector<int> path;
function<void(int, int)> dfs = [&](int i, int t) {
int d = k - path.size(); // 还要选 d 个数
if (t < 0 or t > (i * 2 - d + 1) * d / 2) // 剪枝
return;
if (d == 0) { // 找到一个合法组合
ans.emplace_back(path);
return;
}
// 不选 i
if (i > d) {
dfs(i - 1, t);
}
// 选 i
path.push_back(i);
dfs(i - 1, t - i);
path.pop_back();
};
dfs(9, n);
return ans;
}
vector<vector<int>> combinationSum32(int k, int n) {
vector<vector<int>> ans;
vector<int> path;
function<void(int, int)> dfs = [&](int i, int t) {
int d = k - path.size(); // 还要选 d 个数
if (t < 0 or t > (i * 2 - d + 1) * d / 2) { // 剪枝
return;
}
if (d == 0) { // 找到一个合法组合
ans.emplace_back(path);
return;
}
for (int j = i; j >= d; j--) {
path.push_back(j);
dfs(j - 1, t - j);
path.pop_back();
}
};
dfs(9, n);
return ans;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 40.1 MB, 提交时间: 2024-04-21 13:43:09
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>(k);
dfs(9, n, k, ans, path);
return ans;
}
private void dfs(int i, int t, int k, List<List<Integer>> ans, List<Integer> path) {
int d = k - path.size(); // 还要选 d 个数
if (t < 0 || t > (i * 2 - d + 1) * d / 2) { // 剪枝
return;
}
if (d == 0) { // 找到一个合法组合
ans.add(new ArrayList<>(path));
return;
}
// 不选 i
if (i > d) {
dfs(i - 1, t, k, ans, path);
}
// 选 i
path.add(i);
dfs(i - 1, t - i, k, ans, path);
path.remove(path.size() - 1); // 恢复现场
}
}
java 解法, 执行用时: 0 ms, 内存消耗: 40 MB, 提交时间: 2024-04-21 13:42:57
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>(k);
dfs(9, n, k, ans, path);
return ans;
}
private void dfs(int i, int t, int k, List<List<Integer>> ans, List<Integer> path) {
int d = k - path.size(); // 还要选 d 个数
if (t < 0 || t > (i * 2 - d + 1) * d / 2) { // 剪枝
return;
}
if (d == 0) { // 找到一个合法组合
ans.add(new ArrayList<>(path));
return;
}
for (int j = i; j >= d; j--) {
path.add(j);
dfs(j - 1, t - j, k, ans, path);
path.remove(path.size() - 1);
}
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2024-04-21 13:42:11
func combinationSum3(k, n int) (ans [][]int) {
path := []int{}
var dfs func(int, int)
dfs = func(i, t int) {
d := k - len(path) // 还要选 d 个数
if t < 0 || t > (i*2-d+1)*d/2 { // 剪枝
return
}
if d == 0 { // 找到一个合法组合
ans = append(ans, slices.Clone(path))
return
}
// 不选 i
if i > d {
dfs(i-1, t)
}
// 选 i
path = append(path, i)
dfs(i-1, t-i)
path = path[:len(path)-1]
}
dfs(9, n)
return
}
func combinationSum32(k, n int) (ans [][]int) {
path := []int{}
var dfs func(int, int)
dfs = func(i, t int) {
d := k - len(path) // 还要选 d 个数
if t < 0 || t > (i*2-d+1)*d/2 { // 剪枝
return
}
if d == 0 { // 找到一个合法组合
ans = append(ans, slices.Clone(path))
return
}
for j := i; j >= d; j-- {
path = append(path, j)
dfs(j-1, t-j)
path = path[:len(path)-1]
}
}
dfs(9, n)
return
}
python3 解法, 执行用时: 34 ms, 内存消耗: 16.5 MB, 提交时间: 2024-04-21 13:41:44
class Solution:
# 枚举选哪个
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
ans = []
path = []
def dfs(i: int, t: int) -> None:
d = k - len(path) # 还要选 d 个数
if t < 0 or t > (i * 2 - d + 1) * d // 2: # 剪枝
return
if d == 0: # 找到一个合法组合
ans.append(path.copy())
return
for j in range(i, d - 1, -1):
path.append(j)
dfs(j - 1, t - j)
path.pop()
dfs(9, n)
return ans
# 选或不选
def combinationSum32(self, k: int, n: int) -> List[List[int]]:
ans = []
path = []
def dfs(i: int, t: int) -> None:
d = k - len(path) # 还要选 d 个数
if t < 0 or t > (i * 2 - d + 1) * d // 2: # 剪枝
return
if d == 0: # 找到一个合法组合
ans.append(path.copy())
return
# 不选 i
if i > d:
dfs(i - 1, t)
# 选 i
path.append(i)
dfs(i - 1, t - i)
path.pop()
dfs(9, n)
return ans
python3 解法, 执行用时: 40 ms, 内存消耗: 14.8 MB, 提交时间: 2022-11-17 22:23:01
from typing import List
class Solution:
def combinationSum3(self, k: int, n: int) -> List[List[int]]:
ans = []
temp = []
def dfs(cur: int, rest: int):
nonlocal temp, ans
# 找到一个答案
if len(temp) == k and rest == 0:
ans.append(temp)
return
# 剪枝：跳过的数字过多，后面已经无法选到 k 个数字
if (len(temp) + 10 - cur < k) or (rest < 0):
return
# 跳过当前数字
dfs(cur+1, rest)
# 选当前数字
temp.append(cur)
dfs(cur+1, rest-cur)
temp = temp[:-1]
dfs(1, n)
return ans
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2022-11-17 21:33:17
func combinationSum3(k int, n int) (ans [][]int) {
var temp []int
var dfs func(cur, rest int)
dfs = func(cur, rest int) {
// 找到一个答案
if len(temp) == k && rest == 0 {
ans = append(ans, append([]int(nil), temp...))
return
}
// 剪枝：跳过的数字过多，后面已经无法选到 k 个数字
if len(temp)+10-cur < k || rest < 0 {
return
}
// 跳过当前数字
dfs(cur+1, rest)
// 选当前数字
temp = append(temp, cur)
dfs(cur+1, rest-cur)
temp = temp[:len(temp)-1]
}
dfs(1, n)
return
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2.6 MB, 提交时间: 2022-11-17 21:32:53
func combinationSum3(k int, n int) (ans [][]int) {
var temp []int
check := func(mask int) bool {
temp = nil
sum := 0
for i := 0; i < 9; i++ {
if 1<<i&mask > 0 {
temp = append(temp, i+1)
sum += i + 1
}
}
return len(temp) == k && sum == n
}
for mask := 0; mask < 1<<9; mask++ {
if check(mask) {
ans = append(ans, append([]int(nil), temp...))
}
}
return
}