Combination Sum

Question

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

Thoughts

refer

深搜, 排序后一个一个往里面加，注意是组合，比如当前加到2了，2还可以加，但2以前的就不能加了。

Solution

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  
        if not k:
            return []
        if not n:
            return []
        self.result = []
        self.k = k
        self.n = n
        curList = []
        self.combineHelper([], 1)
        return self.result

    def combineHelper(self, curList, pos):
        if len(curList) == self.k:
            newList = list(curList)
            self.result.append(newList)

        for i in range(pos, self.n+1):
            curList.append(i)
            self.combineHelper(curList, i+1)
            curList.pop()