77. Combinations

link

First idea

Time complexity similar to C(n, k) * k (when you copy array, need k time)

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        res = []

        def backtrack(i, current):
            if len(current) == k:
                res.append(current.copy())
                return
            if i == n+1:
                return

            for i in range(i, n+1):
                current.append(i)
                backtrack(i+1, current)
                current.pop()

        backtrack(1, [])

        return res

Do with pick or not pick Useful for many dp backtrack

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        
        res = []

        def backtrack(i, current):
            if len(current) == k:
                res.append(current.copy())
                return
            if i == n+1:
                return

            # pick
            backtrack(i+1, current + [i])
            # not pick
            backtrack(i+1, current)

        backtrack(1, [])

        return res