Core Concept

Backtracking is a systematic search technique that explores all possible solutions by building candidates incrementally and abandoning ("backtracking") a candidate as soon as it determines that the candidate cannot possibly lead to a valid solution.

Problems Addressed

Backtracking effectively solves the following categories of combinatorial problems:

1. Combination Problems: Find all possible combinations of k elements from [1,2,3,4]
2. Partitioning Problems: Given a string, determine valid partition strategies where all substrings are palindromes
3. Subset Problems: Find all possible subsets of [1,2,3,4]
4. Permutation Problems: Generate all arrangements where order matters (or does not, depending on requirements)
5. Grid and Board Problems: Solve puzzles like N-Queens, Sudoku, and other constraint satisfaction scenarios

Tree Structure Visualization

The backtracking process can be visualized as a tree structure where:

• Each node represents a partial solution
• Branching occurs at each decision point
• Leaves represent complete solutions or dead ends
• The search systematically explores all paths before returning

Standard Backtracking Template

def backtracking(parameters):
    if termination_condition_met():
        store_result()
        return
    
    for each_element in current_level_collection:
        process_current_node()
        backtracking(path, remaining_choices)  # recursive call
        undo_last_operation()  # backtrack

Three-Step Framework

1. Define Parameters: Determine what arguments the backtracking function needs (current path, selection list, starting index, etc.)
2. Establish Termination: Identify when a complete solution is found
3. Implement Search Logic: Design how to traverse choices at each level and handle backtracking

Practical Examples

Example 1: Letter Combinations from Phone Keypad

Given a string containing digits 2-9, generate all possible letter combinations those digits could represent.

Mapping Table

PHONE_MAP = [
    "",    # 0
    "",    # 1
    "abc", # 2
    "def", # 3
    "ghi", # 4
    "jkl", # 5
    "mno", # 6
    "pqrs", # 7
    "tuv",  # 8
    "wxyz", # 9
]

Implementation

class Solution:
    def __init__(self):
        self.result = []
        self.current_path = []
    
    def generate_combinations(self, digits: str) -> list[str]:
        if not digits:
            return self.result
        
        digit_mapping = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        self._backtrack(digits, digit_mapping, 0)
        return self.result
    
    def _backtrack(self, digits: str, mapping: list, position: int) -> None:
        if position == len(digits):
            self.result.append(''.join(self.current_path))
            return
        
        current_letters = mapping[int(digits[position])]
        for letter in current_letters:
            self.current_path.append(letter)
            self._backtrack(digits, mapping, position + 1)
            self.current_path.pop()

Example 2: Palindrome Partitioning

Given a string, partition it such that every substring in each partition is a palindrome.

class Solution:
    def __init__(self):
        self.valid_partitions = []
    
    def partition(self, s: str) -> list[list[str]]:
        self.partitions = []
        self._search(s, 0, [])
        return self.partitions
    
    def _search(self, s: str, start: int, path: list[str]) -> None:
        if start == len(s):
            self.partitions.append(path.copy())
            return
        
        for end in range(start + 1, len(s) + 1):
            segment = s[start:end]
            if self._is_palindrome(segment):
                path.append(segment)
                self._search(s, end, path)
                path.pop()
    
    def _is_palindrome(self, substring: str) -> bool:
        return substring == substring[::-1]

Example 3: Subset Generation

Generate all possible subsets of a given set.

class Solution:
    def __init__(self):
        self.subsets = []
    
    def get_all_subsets(self, nums: list[int]) -> list[list[int]]:
        self._collect_subsets(nums, 0, [])
        return self.subsets
    
    def _collect_subsets(self, nums: list[int], index: int, current: list[int]) -> None:
        self.subsets.append(current.copy())
        
        for i in range(index, len(nums)):
            current.append(nums[i])
            self._collect_subsets(nums, i + 1, current)
            current.pop()

Handling Duplicates in Subsets

When duplicate elements exist, sort the array first and skip duplicates at the current recursion level:

class Solution:
    def subsets_with_dup(self, nums: list[int]) -> list[list[int]]:
        nums.sort()
        self.result = []
        self._generate(nums, 0, [])
        return self.result
    
    def _generate(self, nums: list[int], index: int, path: list[int]) -> None:
        self.result.append(path.copy())
        
        previous = None
        for i in range(index, len(nums)):
            if previous == nums[i]:
                continue
            previous = nums[i]
            path.append(nums[i])
            self._generate(nums, i + 1, path)
            path.pop()

Key Takeaways

• Backtracking transforms exponential-time brute-force searches into manageable recursive solutions
• The tree structure visualization helps understand the exploration pattern
• Proper backtracking (undoing operations) is essential to maintain correct state across recursive calls
• Template-based approaches provide consistent structure for solving diverse backtracking problems
• Sorting and deduplication techniques are crucial for handling duplicate elements efficiently