Combinations

Newbie Developer
1 min readFeb 26, 2021

--

Given two integers n and k, return all possible combinations of k numbers out of 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],
]

Example 2:

Input: n = 1, k = 1
Output: [[1]]

两个值n,k。找出从1…n里挑选k个数的方法

Backtracking 回溯法

先选定一个值,修改当前数组

递归当前节点

改回当前数组

逻辑:

在outermost layer,所有带有当前数值i的permutation都被遍历过了

所以后面的选择不应该包括i。

比如:

N = 4, K = 2.

helper(1, [])
helper(2, [1])
helper(3, [1, 2])
helper(4, [1, 3])
helper(5, [1, 4])

helper(3, [2])
helper(4, [2, 3])
helper(5, [2, 4])

helper(4, [3])
helper(5, [3, 4])

helper(5, [4])

call stack里,当前数值为1时,所有包含1的permutation都被遍历过了。

所以后面的permutation不应该包含1,thus i in range(pos,n)

PS:

使用i in range(pos, n-k+2)会更快

why?

比如4选2里 1,2,3,4

i最多可以到n-k+1 = 3,因为选4的话,没有第二个数可以选。

Solution

class Solution(object):
def combine(self, n, k):
self.ans = []
nums = [0 for _ in range(k)]
count = 0
self.backTrack(1, count, n, k, nums)
return self.ans


def backTrack(self, pos, count, n, k, nums):
if k==0:
self.ans.append(list(nums))
return
for i in range(pos, n-k+2):
nums[count] = i
count += 1
self.backTrack(i+1, count, n, k-1, nums)
count -= 1

--

--