给定两个整数 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 <= 20
1 <= k <= n
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/combinations
参考：
python
# 0077.组合
class Solution:
def combine(self, n: int, k: int) ->[[int]]:
"""
回溯法-解决k层循环问题
:param n:
:param k:
:return:
"""
res = []
path = []
def backtracking(n, k, startIndex):
if len(path) == k:
res.append(path[:])
return
for i in range(startIndex, n+1):
path.append(i)
backtracking(n, k, i+1)
path.pop() # 回溯
backtracking(n, k, 1)
return res
class Solution1:
def combine(self, n: int, k: int) ->[[int]]:
"""
回溯法-解决k层循环问题-剪枝优化版本
:param n:
:param k:
:return:
"""
res = []
path = []
def backtracking(n, k, startIndex):
if len(path) == k:
res.append(path[:])
return
# for广度遍历时，不必到n，根据k决定深度，最后可以遍历的起始值应该为 n-(k-len(path))+1
for i in range(startIndex, n-(k-len(path))+2):
path.append(i)
backtracking(n, k, i+1)
path.pop() # 回溯
backtracking(n, k, 1)
return res
golang
package backTrack
var res [][]int
// 回溯法-不剪枝
func combine(n, k int) [][]int {
if n <= 0 || k <= 0 || k > n {
return res
}
backtrack(n, k, 1, []int{})
return res
}
func backtrack(n,k,startIndex int, track []int) {
if len(track) == k {
tmp := make([]int, k)
copy(tmp, track)
res = append(res, tmp)
}
/*
if len(track)+n-startIndex+1 < k {
return
}
*/
for i:=startIndex;i<=n;i++ {
track = append(track, i)
backtrack(n,k,i+1,track)
track = track[:len(track)-1]
}
}
// 带剪枝回溯
func backtrack1(n,k,startIndex int, track []int) {
if len(track) == k {
tmp := make([]int, k)
copy(tmp, track)
res = append(res, tmp)
}
// i只需要满足 最后一个遍历值为 n-(k-len(tarck))+1
if len(track)+n-startIndex+1 < k {
return
}
for i:=startIndex;i<=n;i++ {
track = append(track, i)
backtrack(n,k,i+1,track)
track = track[:len(track)-1]
}
}