I’ve been working on backtracking problems. For this one, it helped to visualize the recursion stack using Python Tutor. Also, I will have to revisit this later as the complexity analysis is out-of-the-ordinary.

---

Solution

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        nums = [n for n in range(1, n + 1)]
        results = []
        def backtrack(nums, result):
            if len(result) == k:
                results.append(result[:])
                return
            
            while nums:
                backtrack(nums[1:], result + [nums.pop(0)])
        
        backtrack(nums, [])
        return results

The time complexity is O(N choose K) since for each frame of the recursion stack, we work on N-i subproblems, where i is from 0 to k. The space complexity is O(k * n choose k) since each result requires k space.