class Solution {
public:
vector<vector<int>> combine(int n, int k) {
}
};
剑指 Offer II 080. 含有 k 个元素的组合
给定两个整数 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
注意：本题与主站 77 题相同： https://leetcode.cn/problems/combinations/
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 6.2 MB, 提交时间: 2022-08-05 15:39:59
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
}