77. Combinations

2019-05-28

77. Combinations

Given two integers _n_ and _k_, return all possible combinations of _k_ numbers out of 1 … _n_.

Example:

1
2
3
4
5
6
7
8
9
10
Input: n = 4, k = 2
Output:
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        self.dfs(range(1,n+1), k, 0, [], res)
        return res

    def dfs(self, nums, k, index, path, res):
        if k == 0:
            res.append(path)
            return # backtracking
        for i in range(index, len(nums)):
            self.dfs(nums, k-1, i+1, path+[nums[i]], res)
-->