Combinations

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