class Solution {
public:
vector<vector<int>> combine(int n, int k) {
}
};
77. 组合
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。
示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
提示：
1 <= n <= 201 <= k <= n原站题解
golang 解法, 执行用时: 8 ms, 内存消耗: 5.9 MB, 提交时间: 2023-06-16 09:51:17
func combine(n, k int) (ans [][]int) {
path := []int{}
var dfs func(int)
dfs = func(i int) {
d := k - len(path) // 还要选 d 个数
if d == 0 {
ans = append(ans, append([]int(nil), path...))
return
}
// 不选 i
if i > d {
dfs(i - 1)
}
// 选 i
path = append(path, i)
dfs(i - 1)
path = path[:len(path)-1]
}
dfs(n)
return
}
python3 解法, 执行用时: 48 ms, 内存消耗: 17.6 MB, 提交时间: 2023-06-16 09:50:52
# 选或不选
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
path = []
def dfs(i: int) -> None:
d = k - len(path) # 还要选 d 个数
if d == 0:
ans.append(path.copy())
return
# 不选 i
if i > d: dfs(i - 1)
# 选 i
path.append(i)
dfs(i - 1)
path.pop()
dfs(n)
return ans
python3 解法, 执行用时: 52 ms, 内存消耗: 17.6 MB, 提交时间: 2023-06-16 09:50:14
# 枚举下一个数选哪个
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
ans = []
path = []
def dfs(i: int) -> None:
d = k - len(path) # 还要选 d 个数
if d == 0:
ans.append(path.copy())
return
for j in range(i, d - 1, -1):
path.append(j)
dfs(j - 1)
path.pop()
dfs(n)
return ans
golang 解法, 执行用时: 4 ms, 内存消耗: 6.3 MB, 提交时间: 2021-07-22 10:30:44
func combine(n int, k int) (ans [][]int) {
// 末尾加一位 n + 1 作为哨兵
temp := make([]int, k+1)
for i := 1; i <= k; i++ {
temp[i-1] = i
}
temp[k] = n+1
for j := 0; j < k; {
comb := make([]int, k)
copy(comb, temp[:k])
ans = append(ans, comb)
// 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t
// 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]
for j = 0; j < k && temp[j]+1 == temp[j+1]; j++ {
temp[j] = j + 1
}
// j 是第一个 temp[j] + 1 != temp[j + 1] 的位置
temp[j]++
}
return
}