卖萌的弱渣

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

For example, If n = 4 and k = 2, a solution is: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

Solution

  • After you add a sublist to a list, later in other recursive, you update the sublist, the list will also be updated.
(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
27
28
29
30

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_helper(self,result,entry,n,k,index,starter):
        if index == k:
            # if you use entry, later if you change entry, the result will be changed.
            new_entry = []
            for j in entry:
                new_entry.append(j)
            result.append(new_entry)
            return

        for i in range(starter,n+1):
            entry.append(i)
            self.combine_helper(result,entry,n,k,index+1,i+1)
            entry.pop()
        return

    def combine(self, n, k):
        # write your code here 
        entry = []
        result = []
        if k > n or n < 1:
            return result

        self.combine_helper(result,entry,n,k,0,1)
        return result