Leetcode 77: Combinations

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

Code

class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        res = []
        path = []
        self.helper(range(1, 1+n), k, 0, path, res)
        return res
    
    def helper(self, l, k, start_idx, path, res):
        if k == 0:
            res.append(list(path))
            return 
        
        for i in xrange(start_idx, len(l)-k+1):
            path.append(l[i])
            self.helper(l, k-1, i+1, path, res) 
            path.pop()

Idea

What I use is backtracking dfs, which is a common algorithm applied in many questions, for example: https//nb4799.neu.edu/wordpress/?p=2416.

The parameters of helper function:

l: the original list containing 1 ~ n

path: the numbers already added into a temporary list 

k: how many numbers still needed to form a combination

start_idx: the next number to be added should be searched in the range from start_idx to end of the original list

res: the result list

Another elegant recursive solution: https://discuss.leetcode.com/topic/12537/a-short-recursive-java-solution-based-on-c-n-k-c-n-1-k-1-c-n-1-k