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 <= 20
• 1 <= k <= n

思路：很明显的一道回溯题，思路不难，主要是如何实现。当k很小的时候，我们可以通过k个for循环嵌套模拟出来，但k是多少，我们就需要写多少个for循环嵌套，暴力显然是不可能做出来的，这就只能利用回溯来解决。不会回溯的建议看一下下面的讲解，主要是学会回溯算法的模板，然后再根据具体的题目更新这个模板即可。

在我的代码中，定义了全局变量result和path，核心是backtracking这个回溯函数，在这个函数中，if是终止条件，当path中数字个数是k个，那就找到了一组我们要的解，放入result退出这一次循环，for是不断地递归调用backtracking这个回溯函数，当然每次的范围不一样，最终返回result。

回溯算法（代码随想录）：带你学透回溯算法（理论篇）| 回溯法精讲！_哔哩哔哩_bilibili

代码（Python）：

class Solution(object):def combine(self, n, k):result = []                               #保存最终的结果path = []                                 #保存每个满足要求的结果def backtracking(n,k,startIndex):if len(path) == k:                    #如果path中有k个数了，就把这个结果放入resultresult.append(path[:])return for x in range(startIndex,n+1):path.append(x)                    backtracking(n,k,x+1)             #递归调用backtrackingpath.pop()                        #回溯backtracking(n,k,1)                       return result