Recursion and Backtracking
Four prompts on the recurse-mutate-undo pattern: subsets, permutations, and combinations. Includes one trace and one bug hunt.
Question Bank
Medium
JavaScript
4 questions
recursion
backtracking
algorithms
interview-prep
429 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.function subsets(nums) {
// TODO: include/exclude recursion
}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.function permutations(nums) {
// TODO: swap into position i, recurse, swap back
}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.function subsets(nums) {
const out = [];
const cur = [];
function dfs(i) {
if (i === nums.length) { out.push(cur.slice()); return; }
dfs(i + 1);
cur.push(nums[i]);
dfs(i + 1);
cur.pop();
}
dfs(0);
return out;
}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.function combinations(n, k) {
const out = [];
const cur = [];
function dfs(start) {
if (cur.length === k) { out.push(cur.slice()); return; }
for (let i = start; i <= n; i++) {
cur.push(i);
dfs(i);
cur.pop();
}
}
dfs(1);
return out;
}