给定两个整数 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