77. Combinations

# Medium

Key idea: backtracking, 回溯法

不难

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        comb = []
        sub = []
        nums = [i for i in range(1, n+1)]
        self.helper(nums, 0, k, comb, sub)
        return comb
        
    def helper(self, nums, i, k, comb, sub):
        # edge case
        if k == 0:
            comb.append(sub[:])
            return
            
        # regular case
        while i < len(nums):
            sub.append(nums[i])
            self.helper(nums, i+1, k-1, comb, sub)
            sub.pop()
            i += 1

Time complexity = $O(A^k_n)$ , time complexity = $O(A^k_n)$