Intermediate LevelData Structures & Algorithms
How does Backtracking work and how do you generate all Subsets?
ā Interview Prompt: Explain backtracking, decision tree exploration, pruning, and generate all subsets (power set) of a given array.
Backtracking is a recursive algorithmic technique that incrementally builds candidates for solutions and abandons (backtracks) a path as soon as it violates constraints.
Template:
```
backtrack(choices, current_state):
if is_solution(current_state): record_solution(); return
for choice in choices:
make_choice()
backtrack(remaining_choices, updated_state)
undo_choice() // BACKTRACK
```
Subsets (Power Set): $O(N \times 2^N)$
At each index, choose to include or exclude the element.
Code Implementation Example
typescript
function subsets(nums: number[]): number[][] {
const result: number[][] = [];
function backtrack(start: number, current: number[]): void {
result.push([...current]); // record current subset
for (let i = start; i < nums.length; i++) {
current.push(nums[i]); // include nums[i]
backtrack(i + 1, current); // recurse
current.pop(); // backtrack (exclude)
}
}
backtrack(0, []);
return result;
}
console.log(subsets([1, 2, 3]));
// [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]š”Backtracking generating all subsets (power set) in O(N Ć 2^N).
šÆ Interview Key Takeaway
Backtracking = DFS + undo. The "make choice ā recurse ā undo choice" template applies to subsets, permutations, combinations, Sudoku, and N-Queens.
#DSA#Backtracking#Subsets#Recursion#Intermediate
Back to all Data Structures & Algorithms Questionsā