LeetCode 78 – Subsets
Return all subsets of a given set of numbers.
Use DFS/backtracking with index pointer.
At each step: choose to include nums[i] or skip it.
Append current path to result at every call.
Base: when index == n.
Time O(n·2ⁿ).
Tag: Backtracking, Power set.
LeetCode 39 – Combination Sum
All unique combinations where candidates sum to target (reuse allowed).
Sort candidates.
Backtrack with start index:
For each candidate ≥ start: add to path, recurse with target - val.
If target == 0 → save path.
Prune when val > target.
Time ~ O(N^(T/min)).
Tag: Backtracking, Pruning.
LeetCode 40 – Combination Sum II
Like Combination Sum, but each number used once.
Sort candidates.
At level, skip duplicates (if i>start and nums[i]==nums[i-1]).
Recurse with i+1.
Same pruning logic.
Tag: Backtracking, Deduplication.
LeetCode 46 – Permutations
All permutations of distinct numbers.
Track used elements in visited.
For each unused num: mark used, add, recurse, unmark.
Base: when path length == n.
Complexity O(n!).
Tag: Backtracking, Permute.
LeetCode 90 – Subsets II
Like Subsets but may contain duplicates.
Sort nums.
Backtrack with index.
At same depth, skip duplicates if nums[i]==nums[i-1].
Append snapshot of path at every call.
Tag: Backtracking, Deduplication.
LeetCode 79 – Word Search
Check if word exists in grid (adjacent letters, no reuse).
For each cell = word[0], run DFS.
Keep visited (or modify board temporarily).
Explore 4 dirs with next char.
Backtrack (restore cell).
Complexity: O(MN·4^L).
Tag: Backtracking, DFS on grid.
LeetCode 131 – Palindrome Partitioning
Partition string into all palindrome substrings.
Backtrack with start index.
For end in [start..n): if s[start:end] is palindrome → recurse from end.
Append path when start==n.
Precompute palindrome table to optimize.
Tag: Backtracking, DP-check.
LeetCode 51 – N Queens
Place n queens on an n×n board (no attacks).
Row-by-row backtracking.
Maintain cols, diag1 (r+c), diag2 (r−c).
At row r: for each col not in sets → place queen, recurse; backtrack.
Collect board on success.
Time O(n!).
Tag: Backtracking, Constraint.
LeetCode 17 – Letter Combinations of a Phone Number
Return all letter strings from digits (2–9).
Map digits → letters.
Backtrack with index: append each letter for current digit.
Base: when index==len(digits).
Complexity: O(3ⁿ–4ⁿ).
Tag: Backtracking, String.
