How do you generate all subsets of an array using backtracking?
At each step, record the current path as a subset, then try adding each remaining element, recurse, and remove it again. An array of n items has 2^n subsets.
Explain it simply
Each element has two choices: in the subset or out. For three items that is 2 x 2 x 2 = 8 subsets, including the empty one.
Backtracking explores this like trying outfits for a college fest. Pick a shirt, then a bag, then shoes; when you have recorded the outfit, undo the last choice and try the next one. The undo step ("pop") is what makes it backtracking.
Example
function subsets(nums) {
const result = [];
const path = [];
function backtrack(start) {
result.push([...path]); // record a copy
for (let i = start; i < nums.length; i++) {
path.push(nums[i]);
backtrack(i + 1);
path.pop(); // undo
}
}
backtrack(0);
return result;
}
console.log(JSON.stringify(subsets([1, 2, 3])));
// Output: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]Complexity
Time O(n * 2^n), space O(n) for the recursion (excluding output).
What to say in the interview
"I use a path array and a recursive function with a start index. Each call records a copy of the path, then loops over later elements, pushes one, recurses with the next index, and pops it. There are 2^n subsets, so time is O(n * 2^n) including copying, and extra space is O(n) for the path."
Common mistakes
- Pushing the path itself instead of a copy, so every result changes later.
- Starting the inner loop from 0 each time, which creates duplicates in different orders.