lintcode152

Posted on | In

Description

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example

Given 

1
2
3
4
5
6
7
8
9
```
[
  [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
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    """
    @param n: Given the range of numbers
    @param k: Given the numbers of combinations
    @return: All the combinations of k numbers out of 1..n
    """
    def combine(self, n, k):
        # write your code here
        self.res = []
        tmp = []
        self.dfs(n, k, 1, 0, tmp)
        return self.res
        
    # 递归的定义：在 [1,2...n] 中找到所有以 tmp 开头的的集合，并放到 res里面
    # cur_start_pos: 表示当前要开始的位置
    # visited_num: 表示已经遍历过的数目
    def dfs(self, n, k, cur_start_pos, visited_num, tmp):
        # 递归的出口:
        if visited_num == k:
            self.res.append(tmp[:])
            return
        # 递归的拆解：
        for i in range(cur_start_pos, n + 1):
            # 将当前的element放在tmp set里面: [1] -> [1, 2]
            tmp.append(i)
            # 进入下一层: n = 4, k = 2, next_start_pos = i + 1 = 3 注意是在tmp最后的一个元素后面开始, visited_num_now = 2, 
            self.dfs(n, k, i + 1, visited_num + 1, tmp)
            # 回溯: [1, 2] -> [1]
            tmp.pop()