LeetCode 77. Combinations

December 21, 2024

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

1class Solution:
2    def combine(self, n: int, k: int) -> List[List[int]]:
3        nums = [n for n in range(1, n + 1)]
4        results = []
5        def backtrack(nums, result):
6            if len(result) == k:
7                results.append(result[:])
8                return
9            
10            while nums:
11                backtrack(nums[1:], result + [nums.pop(0)])
12        
13        backtrack(nums, [])
14        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.

LeetCode 133. Clone Graph

LeetCode 22. Generate Parentheses