77.md

Combinations

Description

link

---

Solution

DFS too slow

Code

O(log(n))

# Recursive
class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        if k == 0:
            return [[]]
        res = []
        for i in range(k, n + 1):
            for pre in self.combine(i - 1, k - 1):
                res.append(pre + [i])
        return res

# DFS
class Solution:
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        self.res = []
        def dfs(path, cur_len, s):
            if cur_len == 0:
                self.res.append(path)
            else:
                for i in range(s, n + 1):
                    dfs(path + [i], cur_len - 1, i + 1)
        dfs([], k, 1)
        return self.res