Combinations
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]]
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