77.Combinations

python

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

        # reverse enumerate
        def dfs(i):
            d = k - len(path)
            if i < d:
                return
            if len(path) == k:
                ans.append(path[:])
                return

            for j in range(i, 0, -1):
                path.append(j)
                dfs(j-1)
                path.pop()
        dfs(n)
        return ans

forward enumerate

python

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

        # answer perspective
        def dfs(i):
            # pruning
            if k - len(path) > n - i + 1:
                return
            if len(path) == k:
                ans.append(path[:])
                return
            if i == n+1:
                return
            for j in range(i, n+1):
                path.append(j)
                dfs(j+1)
                path.pop()
        dfs(1)
        return ans

choose or not

python

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

        # choose or not
        def dfs(i):
            if len(path) == k:
                ans.append(path[:])
                return
            if i == n+1:
                return
            # not choose
            dfs(i+1)

            # choose
            path.append(i)
            dfs(i+1)
            path.pop()
        dfs(1)
        return ans