Backtracking Theory Overview

Backtracking is an algorithmic technique used to solve problems recursively by trying to build a solution incrementally. It explores potential candidates step-by-step and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly lead to a valid solution.

Common Problem Types:

• Combinations: Selecting k elements from a set of n numbers.
• Partitioning: Dividing a string according to specific rules.
• Subsets: Finding all valid subsets from a collection.
• Permutations: Arranging elements where order matters.
• Board Problems: Solving puzzles like N-Queens or Sudoku.

Conceptual Model:

All backtracking algorithms can be visualized as traversing an N-ary tree. The depth of the tree represents the number of decisions made, while the width represents the choices available at each decision point.

Generic Template Structure:

def backtrack(args):
    # Termination Condition
    if condition_met:
        return

    # Iterative Choice Selection
    for choice in choices:
        # Make the choice
        process_node()
        
        # Recurse
        backtrack(new_args)
        
        # Undo the choice (Backtrack)
        undo_process()

LeetCode 77: Combinations

This problem requires generating all possible combinations of k numbers chosen from the range [1, n].

The core logic involves controlling the recursion depth with a loop. Each level of recursion corresponds to one iteration of a for-loop.

Basic Implementation

In the initial version, we iterate through the entire range at every step, wich results in redundant computation.

class Solution:
    def generate_combinations(self, n: int, k: int):
        result = []
        current_path = []
        
        def dfs(start: int, k_left: int):
            # Base Case: Target length reached
            if k_left == 0:
                result.append(current_path.copy())
                return

            # Recursive Step: Iterate through options
            for i in range(start, n + 1):
                current_path.append(i)
                dfs(i + 1, k_left - 1)
                current_path.pop()  # Backtrack

        dfs(1, k)
        return result

Optimization via Pruning

To improve efficiency, we can calculate the valid range of the loop limit. If we need k elements total and currently have len(path) elements, we only need to select k - len(path) more. We must leave enough remaining numbers to fulfill this requirement. Thus, the starting point i does not need to exceed a certain threshold.

class Solution:
    def combine_optimized(self, n: int, k: int) -> List[List[int]]:
        result = []
        
        def dfs(start: int, path: List[int]):
            if len(path) == k:
                result.append(path[:])
                return
            
            # Pruning calculation: 
            # Remaining needed = k - len(path)
            # Max start index = n - (Remaining needed) + 1
            # Range upper bound (exclusive) = n - (Remaining needed) + 2
            max_start = n - (k - len(path)) + 2
            
            for i in range(start, max_start):
                path.append(i)
                dfs(i + 1, path)
                path.pop()

        dfs(1, [])
        return result

LeetCode 216: Combination Sum III

This variation restricts the combination to using only numbers 1 through 9. The goal is to find all unique combinations of k numbers that sum up to a target value n.

The search space is strictly limited to digits 1-9. Pruning is applied based on the current sum exceeding the target before completing the recursion depth.

class Solution:
    def combinationSum3(self, k: int, n: int) -> List[List[int]]:
        res = []
        
        def dfs(idx: int, target: int, count: int, path: List[int], current_sum: int):
            # Optimization: Current sum exceeds target
            if current_sum > target:
                return
            
            # Termination: Count reached
            if count == k:
                if current_sum == target:
                    res.append(path[:])
                return
            
            # Search Space: 1 to 9
            # Pruning based on remaining slots
            max_val = 9 - (k - count) + 1
            
            for i in range(idx, max_val + 1):
                path.append(i)
                dfs(i + 1, target, count + 1, path, current_sum + i)
                path.pop()

        dfs(1, n, 0, [], 0)
        return res

LeetCode 17: Letter Combinations of a Phone Number

This problem maps digits to their corresponding characters (e.g., '2' -> "abc"). The task is to find all letter combinations representing a given phone number digit string.

We treat the digit string indices as the depth of recursion. For each index, we iterate through the character list associated with that digit.

class Solution:
    def __init__(self):
        # Mapping from digit to string characters
        self.digit_map = {
            "2": "abc", "3": "def", "4": "ghi", 
            "5": "jkl", "6": "mno", "7": "pqrs", 
            "8": "tuv", "9": "wxyz"
        }
        self.outcome = []

    def letterCombinations(self, digits: str) -> List[str]:
        if not digits:
            return []
            
        self._backtrack(digits, 0, "")
        return self.outcome

    def _backtrack(self, digits: str, index: int, current_string: str):
        # Base Case: Traversed all digits
        if index == len(digits):
            self.outcome.append(current_string)
            return

        # Retrieve characters for current digit
        mapped_chars = self.digit_map[digits[index]]

        # Iterate over characters
        for char in mapped_chars:
            # Extend current path
            self._backtrack(digits, index + 1, current_string + char)