题目描述
给定两个整数 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 个当中选 k 个的所有方案对应的枚举是组合型枚举。我们可以使用递归来实现组合型枚举。
一个长度为n 的序列 a的所有子序列，代码框架是这样的：
vector<int> temp;
void dfs(int cur, int n) {
if (cur == n + 1) {
// 记录答案
// ...
return;
}
// 考虑选择当前位置
temp.push_back(cur);
dfs(cur + 1, n, k);
temp.pop_back();
// 考虑不选择当前位置
dfs(cur + 1, n, k);
}
static public func combine2(_ n: Int, _ k: Int) -> [[Int]] {
var res = [[Int]]()
var output = [Int]()
backtrackCombine2(n, k, &res, &output, 1)
return res
}
static func backtrackCombine2(_ n:Int, _ k:Int, _ res:inout [[Int]], _ output:inout [Int], _ cur:Int) {
// 剪枝：temp 长度加上区间 [cur, n] 的长度小于 k，不可能构造出长度为 k 的 temp
if output.count + (n-cur+1) < k {
return
}
// 记录合法的答案
if output.count == k {
res.append(output)
return
}
// 考虑选择当前位置
output.append(cur)
backtrackCombine2(n, k, &res, &output, cur+1)
// 考虑不选择当前位置
output.removeLast()
backtrackCombine2(n, k, &res, &output, cur+1)
}
思路2:使用排列
static public func combine1(_ n: Int, _ k: Int) -> [[Int]] {
var res = [[Int]]()
var output = [Int]()
for i in 0..<n {
output.append(I+1)
}
backtrackCombine1(n, k, &output, &res, 0)
return res
}
static func backtrackCombine1(_ n :Int, _ k :Int, _ output:inout [Int], _ res:inout [[Int]], _ first:Int) {
if first == k {
let temp = output[0..<first]
res.append(Array(temp))
return
}
for i in first..<n {
if first == 0 {
output.swapAt(i, first)
backtrackCombine1(n, k, &output, &res, first+1)
output.swapAt(i, first)
}else {
if output[first-1] < (i+1) {
output.swapAt(i, first)
backtrackCombine1(n, k, &output, &res, first+1)
output.swapAt(i, first)
}
}
}
}
思路3：非递归（字典序法）实现组合型枚举
假设我们把原序列中被选中的位置记为1，不被选中的位置记为0，对于每个方案都可以构造出一个二进制数。我们让原序列从大到小排列（即{n,n−1,⋯1,0}）。我们先看一看n=4，k=2 的例子：
我们可以看出「对应的二进制数」一列包含了由k个1和n−k个0组成的所有二进制数，并且按照字典序排列。这给了我们一些启发，我们可以通过某种方法枚举，使得生成的序列是根据字典序递增的。我们可以考虑我们一个二进制数数字x，它由k个1和n−k 个0组成，如何找到它的字典序中的下一个数字next(x)，这里分两种情况：
规则一：
x 的最低位为1，这种情况下，如果末尾由t个连续的1，我们直接将倒数第t位的1和倒数第t+1 位的0 替换，就可以得到next(x)。如0011→0101，0101→0110，1001→1010，1001111→1010111。
规则二：
x的最低位为0，这种情况下，末尾有t个连续的0，而这t个连续的0之前有m 个连续的1，我们可以将倒数第t+m 位置的1和倒数第t+m+1 位的0 对换，然后把倒数第t+1 位到倒数第t+m−1 位的1移动到最低位。如0110→1001，1010→1100，1011100→1100011。
至此，我们可以写出一个朴素的程序，用一个长度为n的0/1 数组来表示选择方案对应的二进制数，初始状态下最低的k位全部为
1，其余位置全部为0，然后不断通过上述方案求next，就可以构造出所有的方案。
实际上 规则一 是规则二在t=0的情况下的特殊情况
在朴素的方法中我们通过二进制数来构造方案，而二进制数是需要通过迭代的方法来获取next的。考虑不通过二进制数，直接在方案上变换来得到下一个方案。假设一个方案从低到高的k个数分别是{a0,a1,...a(k-1)},
我们可以从低位向高位找到第一个j使得a(j)+1不等于a(j+1)，我们知道出现在a序列中的数字在二进制数中对应的位置一定是1，
即表示被选中，那么a(j)+1不等于a(j+1)意味着a(j)和a(j+1)对应的二进制位中间有0，即这两个1不连续。
我们把a(j)对应的1向高位推送，也就对应着a(j)<a(j)+1，
而对于i∈[0,j−1]内所有的a(i)把值恢复成i+1，即对应这j个1被移动到了二进制数的最低j位。
这似乎只考虑了上面的「规则二」。但是实际上「规则一」是「规则二」在t=0 时的特殊情况，因此这么做和按照两条规则模拟是等价的。
在实现的时候，我们可以用一个数组temp 来存放a 序列，一开始我们先把1到k按顺序存入这个数组，他们对应的下标是0 到k−1。为了计算的方便，我们需要在下标k的位置放置一个哨兵n+1。然后对这个temp 序列按照这个规则进行变换，每次把前k位（即除了最后一位哨兵）的元素形成的子数组加入答案。
每次变换的时候，我们把第一个a(j)+1 ≠ a(j+1)的j找出，使a(j)自增1，同时对i∈[0,j−1] 的a(i)重新置数。如此循环，直到temp 中的所有元素为n内最大的k个元素。
回过头看这个思考题，它是为了我们判断退出条件服务的。我们如何判断枚举到了终止条件呢？其实不是直接通过temp 来判断的，我们会看每次找到的j 的位置，如果j=k 了，就说明[0,k−1] 内的所有的数字是比第k位小的最后k 个数字，这个时候我们找不到任何方案的字典序比当前方案大了，结束枚举。
static public func combine3(_ n: Int, _ k: Int) -> [[Int]] {
var res = [[Int]]()
var temp = [Int]()
// 初始化
// 将 temp 中 [0, k - 1] 每个位置 i 设置为 i + 1，即 [0, k - 1] 存 [1, k]
// 末尾加一位 n + 1 作为哨兵
for i in 1...k {
temp.append(i)
}
temp.append(n+1)
var j = 0
while j<k {
res.append(temp.suffix(k))
// 寻找第一个 temp[j] + 1 != temp[j + 1] 的位置 t
// 我们需要把 [0, t - 1] 区间内的每个位置重置成 [1, t]
j = 0
while j<k && temp[j] + 1 == temp[j+1] {
temp[j] = j+1
j += 1
}
temp[j] = temp[j]+1
}
return res
}
参考：https://leetcode-cn.com/problems/combinations
https://leetcode-cn.com/problems/combinations/solution/zu-he-by-leetcode-solution/
