Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order.
Example 1: Input: n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
- code dfs
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
result = []
def gen_comb(start, cur_comb):
if k == len(cur_comb):
result.append(cur_comb[:])
else:
for i in range(start, n+1):
cur_comb.append(i)
gen_comb(i+1, cur_comb)
cur_comb.pop()
gen_comb(start=1, cur_comb=[])
return result
Python by DFS + backtracking [w/ Comment] - LeetCode Discuss
- code backtracking
class Solution:
def combine(self, n, k):
res = []
def backtracking(nums, path, res):
if len(path) == k:
res.append(path)
for i in range(len(nums)):
backtracking(nums[i+1:], path + [nums[i]], res)
backtracking(list(range(1, n+1)), [], res)
return res