卖萌的弱渣

I am stupid, I am hungry.

Combinations

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

Example,

If n = 4 and k = 2, a solution is:

1
2
3
4
5
6
7
8

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution

(Combinations.py) download
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

class Solution(object):
    def recur_combine(self, result, vector, i, n, k):
        if len(vector) == k:
            result.append(vector[:])
            return

        while i <= n:
            vector.append(i)
            self.recur_combine(result,vector,i+1,n,k)
            vector.pop()
            i = i+1
        return


    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """

        result = []
        if n < k:
            return result
        self.recur_combine(result, [], 1, n, k)
        return result