Leetcode 77. Combinations

https://leetcode.com/problems/combinations/

DFS.

Solution:

# T:O(n!) S:O(n)
class Solution:
    # @return a list of lists of integers
    def combine(self, n, k):
        def dfs(start, valuelist):
            if self.count == k: 
                ret.append(valuelist)
                return
            for i in range(start, n + 1):
                self.count += 1
                dfs(i + 1, valuelist + [i])
                self.count -= 1

        ret, self.count = [], 0
        dfs(1, [])
        return ret

Run Time: 88 ms