Question Bank
Recursion and Backtracking
Difficulty: Medium
Four prompts on the recurse-mutate-undo pattern: subsets, permutations, and combinations. Includes one trace and one bug hunt.
Recursion and Backtracking
Four prompts on the recurse-mutate-undo pattern: subsets, permutations, and combinations. Includes one trace and one bug hunt.
427 views
10
Implement subsets(nums) returning all 2^n subsets of nums (no duplicates assumed). Use recursion with the include / exclude branch.
Examples
Example 1:
Input: nums = [1, 2, 3]
Output: 8 subsets, for example [[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
Explanation: At each index, recurse twice: exclude nums[i], then include nums[i]. The 2^n leaves are the subsets. O(n * 2^n) to emit copies, O(n) stack.Implement permutations(nums) returning all n! orderings using the swap-in-place backtracking pattern.
Examples
Example 1:
Input: nums = [1, 2, 3]
Output: 6 orderings including [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]
Explanation: At depth i, swap each later index j >= i into position i, recurse on i + 1, then swap back. Leaves at depth n emit a copy of nums. O(n * n!) time, O(n) stack.Trace it. For nums = [1, 2], list every value of cur that is emitted by the function below, in order.
Examples
Example 1:
Input: nums = [1, 2]
Output: emission order is [], [2], [1], [1, 2]
Explanation: The recursion exhausts the exclude branch first, emitting [] then [2]. Backtracking pops 2, takes the include branch for index 0, and emits [1] then [1, 2]. Total of 2^2 = 4 subsets.Spot the bug. combinations(n, k) should return all k-sized subsets of 1..n. The current version returns each combination twice.
Examples
Example 1:
Input: n = 3, k = 2
Output (buggy version): 6 entries including duplicates like [1, 1]
Output (fixed version): [[1, 2], [1, 3], [2, 3]]
Explanation: The bug calls dfs(i) instead of dfs(i + 1), so the same element can be reselected at the next depth (combinations with repetition). The fix enforces strictly increasing indices.