Backtracking

Use when: Generate all combinations/permutations/subsets, constraint satisfaction.

Complexity: O(N! or 2^N) depending on problem

Subsets

def subsets(nums):
    result = []
 
    def backtrack(start, current):
        result.append(list(current))
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
 
    backtrack(0, [])
    return result

Combinations

def combinations(nums, k):
    result = []
 
    def backtrack(start, current):
        if len(current) == k:
            result.append(list(current))
            return
        for i in range(start, len(nums)):
            current.append(nums[i])
            backtrack(i + 1, current)
            current.pop()
 
    backtrack(0, [])
    return result

Permutations

def permutations(nums):
    result = []
 
    def backtrack(current, remaining):
        if not remaining:
            result.append(list(current))
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
 
    backtrack([], nums)
    return result

With Pruning (e.g. sum constraint)

def combination_sum(candidates, target):
    result = []
 
    def backtrack(start, current, remaining):
        if remaining == 0:
            result.append(list(current))
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # pruning - candidates sorted
            current.append(candidates[i])
            backtrack(i, current, remaining - candidates[i])  # i not i+1: reuse allowed
            current.pop()
 
    candidates.sort()
    backtrack(0, [], target)
    return result

Signals in a Problem

• “All combinations/permutations/subsets”
• “Generate all valid…”
• Constraint satisfaction (N-Queens, Sudoku)