Q39: Subsets (Power Set Backtracking)
Given an integer array nums of unique elements, return all possible subsets (the power set) using Backtracking.
Backtracking Power Set Generator
function subsets(nums) {
const result = [];
function backtrack(index, current) {
result.push([...current]);
for (let i = index; i < nums.length; i++) {
current.push(nums[i]);
backtrack(i + 1, current);
current.pop(); // Backtrack step
}
}
backtrack(0, []);
return result;
}
console.log(subsets([1, 2, 3]));
// [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]💡 Saves candidate array snapshot at every recursion step, iterates choices from current index, pushes choice, recurses, and pops choice to explore state options.
Key Takeaways
- Generates $2^n$ total subsets.
- Backtracking pattern: 1) Include choice, 2) Recurse, 3) Pop choice (backtrack).
Knowledge Check
How many total subsets exist for a set containing N unique elements?