DSA Fundamentals: Backtracking - From Theory to LeetCode Practice
Master backtracking algorithms through theory and practical LeetCode problem solving. Covering recursive backtracking, exhaustive search, decision trees, and constraint satisfaction problems.
Backtracking is a powerful algorithmic technique for solving constraint satisfaction problems by systematically exploring all possible solutions. It builds solutions incrementally, abandoning partial solutions (backtracking) when they cannot lead to a valid complete solution. This technique is essential for problems involving permutations, combinations, and exhaustive search.
This comprehensive guide combines theoretical understanding with practical problem-solving, featuring solutions to essential LeetCode problems that demonstrate core backtracking patterns.
Understanding Backtracking
Backtracking Fundamentals
Backtracking is a systematic method for solving problems by trying partial solutions and then abandoning them ("backtracking") if they cannot be completed to a valid solution. It's essentially a refined form of brute-force search with pruning.
The Backtracking Process
Core Pattern:
- Make decision - Choose an option at current step
- Recursion - Recursively solve the subproblem
- Base case - Check if solution is complete
- Undo decision - Backtrack by removing the choice
def backtrack(decision_space, current_solution):
# Base case: solution is complete
if is_complete(current_solution):
record_solution(current_solution)
return
# Try each possible choice
for choice in decision_space:
# Make decision
current_solution.append(choice)
# Check if valid (pruning)
if is_valid(current_solution):
# Recursion
backtrack(decision_space, current_solution)
# Undo decision (backtrack)
current_solution.pop()
When to Use Backtracking
Backtracking is ideal for:
- Exhaustive search - Finding all solutions
- Constraint satisfaction - Problems with constraints
- Decision trees - Problems with multiple choices at each step
- Combinatorial problems - Permutations, combinations, subsets
- Path finding - Finding all paths in graphs/grids
Common problem types:
- Generate all subsets/combinations/permutations
- Find all valid configurations (N-Queens, Sudoku)
- String generation with constraints
- Path finding with constraints
- Partition problems
Backtracking vs Other Techniques
| Aspect | Backtracking | Dynamic Programming | Greedy |
|---|---|---|---|
| Purpose | Find all solutions | Find optimal solution | Find optimal solution |
| Approach | Explore all possibilities | Build from subproblems | Make local choices |
| Pruning | Prune invalid paths | Memoize results | No reconsideration |
| Time complexity | Often exponential | Usually polynomial | Usually linear |
| Space complexity | O(depth) recursion stack | O(n) or O(n²) table | O(1) |
| When to use | Need all solutions | Overlapping subproblems | Greedy choice property |
Key Backtracking Patterns
1. Subset Generation:
- For each element: include or exclude
- Build solution incrementally
- Backtrack after exploring both choices
2. Permutation Generation:
- Try each unused element at current position
- Track used elements
- Backtrack to try other elements
3. Constraint Satisfaction:
- Check constraints before recursing
- Prune invalid paths early
- Build valid solutions incrementally
4. 2D Grid Backtracking:
- Explore in 4 directions (up, down, left, right)
- Mark visited cells
- Unmark when backtracking
Time Complexity Analysis
| Pattern | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Subsets | O(2^n) | O(n) | 2^n subsets, each O(n) space |
| Permutations | O(n! × n) | O(n) | n! permutations |
| Combinations | O(2^n) | O(n) | Similar to subsets |
| Constraint problems | O(b^d) | O(d) | b = branching factor, d = depth |
| 2D Grid | O(4^m) | O(m) | m = path length |
Essential LeetCode Problems & Solutions
Let's explore fundamental backtracking problems that demonstrate core recursive patterns.
1. Subsets (LeetCode 78)
Problem: Given an array of unique integers, return all possible subsets (power set).
Approach: For each element, make two choices: include it or skip it. Use backtracking to explore both choices.
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res, cur = [], []
def dfs(index):
# Base case: processed all elements
if len(nums) == index:
res.append(cur[:]) # Copy current subset
return
# Choice 1: Skip current element
dfs(index + 1)
# Choice 2: Include current element
cur.append(nums[index])
dfs(index + 1)
# Backtrack: undo the choice
cur.pop()
dfs(0)
return res
Time Complexity: O(2^n × n) - 2^n subsets, each takes O(n) to copy
Space Complexity: O(n) - Recursion stack depth + current subset
Key Concepts:
- Two choices per element: Include or exclude
- Base case: When index equals array length
- Copy before appending:
cur[:]creates a copy (important!) - Backtracking: Remove element after recursion to try other paths
- Decision tree: Each level represents one element, two branches per level
Example Walkthrough:
Input: [1, 2, 3]
Decision tree:
[]
/ \
[] [1]
/ \ / \
[] [2] [1] [1,2]
/ \ / \ / \ / \
[] [3] [2] [2,3] [1] [1,3] [1,2] [1,2,3]
Result: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]
Why Copy is Important:
curis a reference, not a copy- Without
cur[:], all entries inreswould reference the same list - After backtracking,
curchanges, affecting all references cur[:]creates a snapshot of current state
2. Permutations (LeetCode 46)
Problem: Given an array of distinct integers, return all possible permutations.
Approach: For each position, try each unused element. Track used elements and backtrack.
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
res, curr = [], []
def dfs():
# Base case: permutation complete
if len(nums) == len(curr):
res.append(curr[:])
return
# Try each unused element
for x in nums:
if x not in curr:
# Make choice
curr.append(x)
# Recurse
dfs()
# Backtrack
curr.pop()
dfs()
return res
Time Complexity: O(n! × n) - n! permutations, each takes O(n) to copy
Space Complexity: O(n) - Recursion stack + current permutation
Key Concepts:
- Position-based: Fill positions one by one
- Unused element check:
if x not in currensures no duplicates - Complete when: Current length equals input length
- Backtracking: Remove element to try other permutations
- All elements used: Unlike subsets, must use all elements
Example Walkthrough:
Input: [1, 2, 3]
Decision tree (first few levels):
[]
/ | \
[1] [2] [3]
/ \ / \ / \
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
Result: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
Optimization Note:
- Using
x not in curris O(n) check - Can optimize with boolean array or set for O(1) lookup
- Trade-off: More space for better time complexity
3. Letter Combinations of a Phone Number (LeetCode 17)
Problem: Given a string of digits, return all possible letter combinations that the number could represent (phone keypad mapping).
Approach: For each digit, try each possible letter. Build string incrementally.
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
h_map = {
"2": "abc", "3": "def",
"4": "ghi", "5": "jkl", "6": "mno",
"7": "pqrs", "8": "tuv", "9": "wxyz"
}
res, curr = [], []
def helper(index):
# Base case: processed all digits
if len(curr) == len(digits):
res.append("".join(curr))
return
# Get letters for current digit
digit = digits[index]
letters = h_map[digit]
# Try each letter for current digit
for char in letters:
curr.append(char)
helper(index + 1)
curr.pop()
if digits: # Handle empty input
helper(0)
return res
Time Complexity: O(4^n × n) - 4^n combinations (worst case), n to join string
Space Complexity: O(n) - Recursion stack + current combination
Key Concepts:
- Digit-by-digit: Process one digit at a time
- Letter mapping: Use dictionary for digit-to-letters mapping
- String building: Use list and join (more efficient than string concatenation)
- Index tracking: Track which digit we're processing
- Empty input: Handle case when digits string is empty
Example Walkthrough:
Input: "23"
h_map["2"] = "abc"
h_map["3"] = "def"
Decision tree:
[]
/ | \
['a'] ['b'] ['c']
/ | \ / | \ / | \
['a','d'] ... ['b','d'] ... ['c','d'] ...
| | |
"ad" "ae" "af" "bd" "be" "bf" "cd" "ce" "cf"
Result: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
4. Combination Sum (LeetCode 39)
Problem: Given an array of distinct integers and a target, find all unique combinations where numbers sum to target. Numbers can be reused.
Approach: For each candidate, decide to use it (and can reuse) or skip it. Track current sum.
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
res, curr = [], []
def helper(index, curr_sum):
# Base case: found valid combination
if curr_sum == target:
res.append(curr[:])
return
# Base case: invalid path (pruning)
if curr_sum > target or index == len(candidates):
return
# Choice 1: Skip current candidate
helper(index + 1, curr_sum)
# Choice 2: Use current candidate (can reuse)
curr.append(candidates[index])
helper(index, curr_sum + candidates[index])
curr.pop()
helper(0, 0)
return res
Time Complexity: O(2^target) - Exponential in worst case
Space Complexity: O(target) - Recursion stack depth
Key Concepts:
- Reuse allowed: Can use same candidate multiple times
- Sum tracking: Track current sum to avoid recomputation
- Pruning: Early return when sum exceeds target
- Two choices: Skip or use (with reuse)
- Index management: Don't advance index when reusing
Example Walkthrough:
Input: candidates = [2, 3, 6, 7], target = 7
Decision tree (simplified):
[]
/ \
[] [2]
/ \ / \
[] [3] [2] [2,2]
/ \ / \ / \ / \
... [7] ... [3,3] [2,2] [2,2,2] [2,2,3]
| |
sum=7 ✓ sum=6, can add 2 or 3
Result: [[2,2,3], [7]]
Key Insight:
- When reusing candidate, keep same index
- When skipping, advance index
- This ensures we try all combinations without duplicates
5. Generate Parentheses (LeetCode 22)
Problem: Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Approach: Track open and close counts. Add '(' when open < n, add ')' when close < open.
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res, curr = [], []
def helper(openn, close):
# Base case: generated n pairs
if len(curr) == (2 * n):
res.append("".join(curr))
return
# Choice 1: Add '(' if we haven't used all open parentheses
if openn < n:
curr.append("(")
helper(openn + 1, close)
curr.pop()
# Choice 2: Add ')' if we have more open than close
if close < openn:
curr.append(")")
helper(openn, close + 1)
curr.pop()
helper(0, 0)
return res
Time Complexity: O(4^n / √n) - Catalan number complexity
Space Complexity: O(n) - Recursion stack + current string
Key Concepts:
- Constraint-based: Two constraints (open < n, close < open)
- Well-formed: Close count must never exceed open count
- Two choices: Add '(' or ')' based on constraints
- Catalan numbers: Number of valid parentheses is nth Catalan number
- Pruning: Invalid states automatically avoided
Example Walkthrough:
Input: n = 3
Decision tree (first few levels):
""
/ \
"(" (invalid: close > open)
/ \
"((" "()"
/ \ / \
"((" "(()" "()(" "()()"
...
Valid paths lead to:
"((()))", "(()())", "(())()", "()(())", "()()()"
Why Constraints Work:
openn < n: Can't have more than n open parenthesesclose < openn: Can't close more than we've opened- These constraints ensure all generated strings are well-formed
6. Combination Sum II (LeetCode 40)
Problem: Given an array of integers (may contain duplicates) and a target, find all unique combinations where numbers sum to target. Each number can only be used once.
Approach: Sort array first. Skip duplicates at same level to avoid duplicate combinations.
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
res, curr = [], []
candidates.sort() # Sort to handle duplicates
def helper(index, curr_sum):
# Base case: found valid combination
if curr_sum == target:
res.append(curr[:])
return
# Base case: invalid path (pruning)
if curr_sum > target or index == len(candidates):
return
# Try each candidate starting from index
for i in range(index, len(candidates)):
# Skip duplicates at same level
if i > index and candidates[i] == candidates[i-1]:
continue
# Use current candidate
curr.append(candidates[i])
helper(i + 1, curr_sum + candidates[i])
curr.pop()
helper(0, 0)
return res
Time Complexity: O(2^n) - Exponential, but pruned
Space Complexity: O(target) - Recursion stack depth
Key Concepts:
- Sorting prerequisite: Must sort to group duplicates together
- Duplicate skipping:
if i > index and candidates[i] == candidates[i-1] - One-time use: Advance index (i + 1) instead of reusing
- Same level check: Only skip if it's not the first occurrence at this level
- Why it works: First occurrence at level is included, subsequent duplicates skipped
Example Walkthrough:
Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
After sort: [1, 1, 2, 5, 6, 7, 10]
At index 0, we can choose:
- 1 (first occurrence) → explore
- Skip duplicate 1 at index 1 (same level)
- Then try 2, 5, 6, 7, 10
This prevents: [1,2,5] and [1,2,5] (duplicate)
Duplicate Handling Logic:
i > index: Not the first candidate at this levelcandidates[i] == candidates[i-1]: Duplicate value- Skip to avoid duplicate combinations
- First occurrence is always tried (can form valid combinations)
7. Subsets II (LeetCode 90)
Problem: Given an array of integers that may contain duplicates, return all possible subsets. Solution set must not contain duplicate subsets.
Approach: Sort array. Skip duplicates at same level when generating subsets.
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res, curr = [], []
nums.sort() # Sort to handle duplicates
def dfs(index):
# Base case: processed all elements
if index == len(nums):
res.append(curr[:])
return
# Choice 1: Include current element
curr.append(nums[index])
dfs(index + 1)
curr.pop()
# Choice 2: Skip current element
# Skip all duplicates at this level
while index + 1 < len(nums) and nums[index] == nums[index + 1]:
index += 1
dfs(index + 1)
dfs(0)
return res
Time Complexity: O(2^n × n) - 2^n subsets, each O(n) to copy
Space Complexity: O(n) - Recursion stack + current subset
Key Concepts:
- Sorting prerequisite: Must sort to group duplicates
- Duplicate skipping: Skip all remaining duplicates when excluding
- Two-phase approach: Include first, then skip all duplicates
- Why it works: Including first occurrence covers all cases with that number
- Alternative approach: Can also use same-level duplicate check like Combination Sum II
Example Walkthrough:
Input: [1, 2, 2]
After sort: [1, 2, 2]
Decision tree:
[]
/ \
[] [1]
/ \ / \
[] [2] [1] [1,2]
/ \ / \ / \ / \
[] [2] [2] [2,2] [1] [1,2] [1,2] [1,2,2]
| | | | | | | |
Skip [2] [2] [2,2] [1] [1,2] [1,2] [1,2,2]
duplicate
Result: [[], [2], [2,2], [1], [1,2], [1,2,2]]
Alternative Implementation:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res, curr = [], []
nums.sort()
def dfs(index):
res.append(curr[:])
for i in range(index, len(nums)):
# Skip duplicates at same level
if i > index and nums[i] == nums[i-1]:
continue
curr.append(nums[i])
dfs(i + 1)
curr.pop()
dfs(0)
return res
8. Word Search (LeetCode 79)
Problem: Given a 2D board and a word, determine if the word exists in the grid. Word can be constructed from adjacent cells (horizontally or vertically).
Approach: Backtracking on 2D grid. Explore 4 directions, mark visited, unmark when backtracking.
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
rows, cols = len(board), len(board[0])
def dfs(row, col, index):
# Base case: found complete word
if index == len(word):
return True
# Base case: out of bounds or character mismatch
if (row < 0 or row >= rows or
col < 0 or col >= cols or
board[row][col] != word[index]):
return False
# Mark as visited (temporarily)
temp = board[row][col]
board[row][col] = '#' # Mark visited
# Explore 4 directions
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for dr, dc in directions:
if dfs(row + dr, col + dc, index + 1):
return True
# Backtrack: unmark
board[row][col] = temp
return False
# Try starting from each cell
for i in range(rows):
for j in range(cols):
if dfs(i, j, 0):
return True
return False
Time Complexity: O(m × n × 4^L) - m×n cells, 4 directions, L = word length
Space Complexity: O(L) - Recursion stack depth
Key Concepts:
- 2D backtracking: Explore grid in 4 directions
- Visited marking: Mark cell as '#' to prevent revisiting
- Backtracking: Restore original character when backtracking
- Early termination: Return True immediately when word found
- Start from any cell: Try all possible starting positions
Example Walkthrough:
Input:
board = [["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]]
word = "ABCCED"
Start at (0,0): 'A' matches
→ Try (0,1): 'B' matches
→ Try (0,2): 'C' matches
→ Try (1,2): 'C' matches
→ Try (2,2): 'E' matches
→ Try (2,1): 'D' matches → Found!
Optimization Notes:
- Can use separate visited matrix instead of modifying board
- Early termination when word found
- Pruning: Check bounds and character match before recursing
9. Palindrome Partitioning (LeetCode 131)
Problem: Given a string, partition it such that every substring is a palindrome. Return all possible palindrome partitioning.
Approach: For each position, try all possible palindrome substrings starting there. Backtrack after each partition.
class Solution:
def partition(self, s: str) -> List[List[str]]:
res, curr = [], []
def is_palindrome(left, right):
# Check if substring is palindrome
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
def dfs(index):
# Base case: processed entire string
if index == len(s):
res.append(curr[:])
return
# Try all possible substrings starting at index
for i in range(index, len(s)):
# Check if substring is palindrome
if is_palindrome(index, i):
# Make choice: add palindrome substring
curr.append(s[index:i+1])
# Recurse on remaining string
dfs(i + 1)
# Backtrack
curr.pop()
dfs(0)
return res
Time Complexity: O(2^n × n) - Exponential partitions, n to check palindrome
Space Complexity: O(n) - Recursion stack + current partition
Key Concepts:
- Partition-based: Divide string into palindrome substrings
- Palindrome check: Verify substring before adding
- Index management: Track where we are in string
- Substring generation: Try all possible ending positions
- Complete when: Index reaches string length
Example Walkthrough:
Input: "aab"
Decision tree:
[]
/ | \
["a"] ["aa"] (invalid: "aab" not palindrome)
/ \ |
["a","a"] ["a","ab"] ["aa","b"]
| (invalid) |
["a","a","b"] (complete)
|
(complete)
Result: [["a","a","b"], ["aa","b"]]
Optimization:
- Can memoize palindrome checks for O(1) lookup
- Precompute palindrome table:
dp[i][j] = is_palindrome(i, j) - Reduces palindrome check from O(n) to O(1)
10. N-Queens (LeetCode 51)
Problem: Place n queens on n×n chessboard such that no two queens attack each other. Return all distinct solutions.
Approach: Place queen row by row. For each row, try each column. Check if placement is valid (no conflicts).
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
board = [['.' for _ in range(n)] for _ in range(n)]
def is_valid(row, col):
# Check column
for i in range(row):
if board[i][col] == 'Q':
return False
# Check diagonal: top-left to bottom-right
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# Check diagonal: top-right to bottom-left
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def dfs(row):
# Base case: placed queens in all rows
if row == n:
# Convert board to required format
solution = [''.join(row) for row in board]
res.append(solution)
return
# Try each column in current row
for col in range(n):
if is_valid(row, col):
# Place queen
board[row][col] = 'Q'
# Recurse to next row
dfs(row + 1)
# Backtrack: remove queen
board[row][col] = '.'
dfs(0)
return res
Time Complexity: O(n!) - Factorial, but heavily pruned
Space Complexity: O(n²) - Board representation
Key Concepts:
- Row-by-row placement: Place one queen per row
- Conflict checking: Check column and both diagonals
- Valid placement: Only place if no conflicts
- Backtracking: Remove queen to try other columns
- Solution format: Convert board to list of strings
Example Walkthrough:
n = 4
Row 0: Try col 0
Row 1: Try col 2 (col 0,1 conflict)
Row 2: Try col 1 (col 0,2 conflict)
Row 3: Try col 3 → Valid! Solution found
[".Q..",
"...Q",
".Q..",
"..Q."]
Backtrack and try other positions...
Optimization:
- Use sets to track occupied columns and diagonals: O(1) check
- Three sets:
cols,diag1(row-col),diag2(row+col) - Reduces validation from O(n) to O(1)
Optimized Version:
def solveNQueens(self, n: int) -> List[List[str]]:
res = []
board = [['.' for _ in range(n)] for _ in range(n)]
cols = set()
diag1 = set() # row - col
diag2 = set() # row + col
def dfs(row):
if row == n:
res.append([''.join(row) for row in board])
return
for col in range(n):
if col not in cols and (row - col) not in diag1 and (row + col) not in diag2:
board[row][col] = 'Q'
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
dfs(row + 1)
board[row][col] = '.'
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
dfs(0)
return res
Core Algorithm Patterns from Today's Problems
1. Subset Generation Pattern
When to use:
- Generate all subsets/combinations
- Each element: include or exclude
- Need power set
Examples: Subsets, Subsets II
Key characteristics:
- Two choices per element: include or skip
- Base case: processed all elements
- Copy current state before adding to result
- O(2^n) time complexity
Template:
def subsets(nums):
res, curr = [], []
def dfs(index):
if index == len(nums):
res.append(curr[:]) # Copy!
return
# Choice 1: Skip
dfs(index + 1)
# Choice 2: Include
curr.append(nums[index])
dfs(index + 1)
curr.pop() # Backtrack
dfs(0)
return res
2. Permutation Generation Pattern
When to use:
- Generate all permutations
- All elements must be used
- Order matters
Examples: Permutations, N-Queens (row placement)
Key characteristics:
- Try each unused element at current position
- Track used elements
- Complete when all positions filled
- O(n!) time complexity
Template:
def permute(nums):
res, curr = [], []
def dfs():
if len(curr) == len(nums):
res.append(curr[:])
return
for x in nums:
if x not in curr:
curr.append(x)
dfs()
curr.pop()
dfs()
return res
3. Constraint-Based Generation Pattern
When to use:
- Generate solutions with constraints
- Need to validate before recursing
- Prune invalid paths early
Examples: Generate Parentheses, Combination Sum, N-Queens
Key characteristics:
- Check constraints before making choice
- Prune invalid branches
- Track state (sum, counts, etc.)
- Early termination when constraint violated
Template:
def constrained_backtrack(state):
res, curr = [], []
def dfs(state):
if is_complete(state):
res.append(curr[:])
return
if is_invalid(state):
return # Prune
for choice in choices:
if is_valid(state, choice):
curr.append(choice)
update_state(state, choice)
dfs(state)
restore_state(state, choice)
curr.pop()
dfs(initial_state)
return res
4. 2D Grid Backtracking Pattern
When to use:
- Problems on 2D grids/boards
- Path finding with constraints
- Mark visited cells
Examples: Word Search, Sudoku Solver
Key characteristics:
- Explore 4 (or 8) directions
- Mark visited cells
- Unmark when backtracking
- Check bounds before recursing
Template:
def grid_backtrack(board, target):
rows, cols = len(board), len(board[0])
def dfs(row, col, state):
if is_complete(state):
return True
if is_invalid(row, col, state):
return False
# Mark visited
temp = board[row][col]
board[row][col] = '#'
# Explore directions
directions = [(0,1), (0,-1), (1,0), (-1,0)]
for dr, dc in directions:
if dfs(row + dr, col + dc, state):
return True
# Backtrack: unmark
board[row][col] = temp
return False
# Try all starting positions
for i in range(rows):
for j in range(cols):
if dfs(i, j, initial_state):
return True
return False
5. Duplicate Handling Pattern
When to use:
- Input contains duplicates
- Need to avoid duplicate solutions
- Must sort first
Examples: Subsets II, Combination Sum II
Key characteristics:
- Sort input first
- Skip duplicates at same level
- Include first occurrence
- Skip subsequent duplicates
Template:
def handle_duplicates(nums):
res, curr = [], []
nums.sort() # Essential!
def dfs(index):
if index == len(nums):
res.append(curr[:])
return
# Include first occurrence
curr.append(nums[index])
dfs(index + 1)
curr.pop()
# Skip all duplicates
while index + 1 < len(nums) and nums[index] == nums[index + 1]:
index += 1
dfs(index + 1)
dfs(0)
return res
Performance Optimization Tips
1. Memoization for Repeated Computations
# Palindrome Partitioning: memoize palindrome checks
memo = {}
def is_palindrome(left, right):
if (left, right) in memo:
return memo[(left, right)]
# ... check logic
memo[(left, right)] = result
return result
Key insight: Cache expensive computations like palindrome checks.
2. Use Sets for O(1) Lookups
# N-Queens: use sets instead of linear search
cols = set()
diag1 = set()
diag2 = set()
# O(1) check instead of O(n)
if col not in cols and (row-col) not in diag1:
# valid
Key insight: Trade space for time when checking membership.
3. Early Pruning
# Combination Sum: prune early
if curr_sum > target:
return # Don't explore further
Key insight: Stop exploring invalid paths immediately.
4. Copy Lists Efficiently
# Always copy when adding to result
res.append(curr[:]) # Correct
res.append(curr) # Wrong: reference, not copy
Key insight: Lists are mutable, always copy before storing.
5. Sort for Duplicate Handling
# Always sort when handling duplicates
nums.sort() # Essential for duplicate skipping to work
Key insight: Sorting groups duplicates together, enabling efficient skipping.
Common Pitfalls and Solutions
1. Forgetting to Copy Lists
# Wrong: Adding reference
res.append(curr) # All entries will be same reference
# Correct: Copy list
res.append(curr[:]) # Creates snapshot
2. Not Backtracking Properly
# Wrong: Forget to undo choice
curr.append(x)
dfs()
# Missing: curr.pop()
# Correct: Always backtrack
curr.append(x)
dfs()
curr.pop() # Undo choice
3. Incorrect Duplicate Handling
# Wrong: Skip all duplicates including first
for i in range(index, len(nums)):
if nums[i] == nums[index]: # Skips first too!
continue
# Correct: Skip only after first
for i in range(index, len(nums)):
if i > index and nums[i] == nums[i-1]: # Keep first
continue
4. Not Checking Bounds in 2D Backtracking
# Wrong: Check after accessing
if board[row][col] == target: # Might be out of bounds!
if row < 0 or row >= rows: # Too late
# Correct: Check bounds first
if row < 0 or row >= rows or col < 0 or col >= cols:
return False
if board[row][col] == target:
# process
5. Incorrect State Management
# Wrong: Modify state incorrectly
state += value
dfs()
state -= value # Might not restore correctly
# Correct: Use temporary or ensure proper restoration
temp = state
state = new_state
dfs()
state = temp # Restore exactly
Time Complexity Comparison
Problem Complexity Summary
| Problem | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Subsets | O(2^n × n) | O(n) | 2^n subsets, n to copy |
| Permutations | O(n! × n) | O(n) | n! permutations |
| Letter Combinations | O(4^n × n) | O(n) | 4^n combinations |
| Combination Sum | O(2^target) | O(target) | Exponential |
| Generate Parentheses | O(4^n / √n) | O(n) | Catalan numbers |
| Word Search | O(m×n×4^L) | O(L) | L = word length |
| Palindrome Partitioning | O(2^n × n) | O(n) | Exponential partitions |
| N-Queens | O(n!) | O(n²) | Factorial, pruned |
Why Backtracking Can Be Expensive
Exponential growth:
- Subsets: 2^n possibilities
- Permutations: n! possibilities
- Constraint problems: Branching factor ^ depth
Optimization strategies:
- Pruning: Eliminate invalid paths early
- Memoization: Cache repeated computations
- Constraint propagation: Reduce search space
- Heuristics: Guide search toward solutions
Conclusion
Backtracking is a fundamental technique for solving constraint satisfaction and exhaustive search problems. Key takeaways:
Core Concepts Mastered:
Backtracking Fundamentals:
- Decision → Recursion → Base case → Undo - Core pattern
- Exhaustive search - Explore all possibilities
- Pruning - Eliminate invalid paths early
- State management - Track and restore state correctly
Problem Types:
- Subset/Combination generation - Include/exclude choices
- Permutation generation - Try all arrangements
- Constraint satisfaction - Validate before recursing
- 2D grid problems - Explore with backtracking
- String partitioning - Divide with constraints
Essential Patterns Mastered Today:
Pattern 1: Subset Generation (Subsets, Subsets II)
Pattern 2: Permutation Generation (Permutations)
Pattern 3: Constraint-Based Generation (Generate Parentheses, Combination Sum)
Pattern 4: 2D Grid Backtracking (Word Search)
Pattern 5: Duplicate Handling (Subsets II, Combination Sum II)
Problem-Solving Strategies:
- Always copy lists before adding to result (
curr[:]) - Sort for duplicates - Essential for duplicate handling
- Prune early - Check constraints before recursing
- Track state properly - Restore state when backtracking
- Use appropriate data structures - Sets for O(1) lookups
- Memoize expensive operations - Palindrome checks, etc.
Optimization Principles:
- Prune invalid paths - Early termination saves time
- Memoize computations - Cache repeated expensive operations
- Use efficient data structures - Sets for membership, arrays for indexing
- Copy efficiently - Use slicing for lists
- Sort when needed - Enables duplicate skipping
When to Use Backtracking:
Use backtracking when:
- Need to find all solutions
- Problem has constraints
- Can make decisions incrementally
- Need exhaustive search
- Problem involves permutations/combinations
Consider alternatives when:
- Only need one solution → DFS/BFS might be simpler
- Need optimal solution → Dynamic programming
- Greedy choice property holds → Greedy algorithm
- Problem has overlapping subproblems → Dynamic programming
Next Steps:
Building on backtracking fundamentals, future topics will cover:
- Dynamic Programming (memoization vs tabulation)
- Advanced Graph Algorithms (DFS, BFS variations)
- Constraint Programming (advanced constraint satisfaction)
- Optimization Techniques (branch and bound, pruning strategies)
The problems covered here represent fundamental backtracking patterns that appear across technical interviews and constraint satisfaction problems. Master these concepts, and you'll be able to systematically solve complex combinatorial and constraint problems.
Practice Problems for Mastery:
Basic Backtracking:
- 78. Subsets
-
- Subsets II
-
- Permutations
-
- Permutations II
-
- Letter Combinations of a Phone Number
-
- Generate Parentheses
Intermediate Backtracking:
- 39. Combination Sum
-
- Combination Sum II
-
- Combinations
-
- Combination Sum III
-
- Palindrome Partitioning
-
- Restore IP Addresses
Advanced Backtracking:
- 51. N-Queens
-
- N-Queens II
-
- Sudoku Solver
-
- Word Search
-
- Word Search II
-
- Word Break II
References:
- NeetCode - Algorithms
- LeetCode Patterns
- Greg Hogg DSA Algorithm YouTube Channel
- Algorithm Design Manual by Steven Skiena
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
- Backtracking Algorithms - GeeksforGeeks
This comprehensive guide combines theoretical understanding with practical problem-solving, providing a solid foundation for mastering backtracking algorithms and constraint satisfaction problems.