# 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 = 2Output:[  [2,4],  [3,4],  [2,3],  [1,2],  [1,3],  [1,4],]`

Example 2:

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

Backtracking 回溯法

`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都被遍历过了。

PS：

why?

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`