Backtracking Patterns: Permutations, Combinations, Subsets, and Constraints

Backtracking is a systematic way to explore all possible solutions by building candidates incrementally and abandoning a candidate as soon as it cannot lead to a valid solution. It is essentially DFS on a decision tree with pruning. This guide covers every major backtracking pattern with templates and LeetCode solutions.

The Core Template

Every backtracking problem follows the same structure.

def backtrack(candidates, path, result, start=0):
    # Base case: found a valid solution
    if is_solution(path):
        result.append(path[:])  # append a copy
        return
    
    # Explore all choices
    for i in range(start, len(candidates)):
        # Pruning: skip invalid choices
        if not is_valid(candidates[i], path):
            continue
        
        # Choose
        path.append(candidates[i])
        
        # Explore
        backtrack(candidates, path, result, i + 1)  # or i for reuse
        
        # Un-choose (backtrack)
        path.pop()

                    []
             /    |    \
          [1]    [2]   [3]
         /  \     |
      [1,2] [1,3] [2,3]
       |
    [1,2,3]

At each node: choose to include or skip each remaining element.
Backtrack by removing the last element after exploring.

Pattern 1: Subsets

Subsets (LC 78)

Generate all subsets of a set of distinct integers.

def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    
    def backtrack(start, path):
        result.append(path[:])  # every path is a valid subset
        
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

// Java version
public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, int start, List<Integer> path,
                       List<List<Integer>> result) {
    result.add(new ArrayList<>(path));
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.remove(path.size() - 1);
    }
}

Subsets II — With Duplicates (LC 90)

def subsetsWithDup(nums: list[int]) -> list[list[int]]:
    nums.sort()  # sort to group duplicates
    result = []
    
    def backtrack(start, path):
        result.append(path[:])
        
        for i in range(start, len(nums)):
            # Skip duplicates at the same level
            if i > start and nums[i] == nums[i - 1]:
                continue
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return result

print(subsetsWithDup([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]]

Pattern 2: Combinations

Combinations (LC 77)

Generate all combinations of k numbers from 1 to n.

def combine(n: int, k: int) -> list[list[int]]:
    result = []
    
    def backtrack(start, path):
        if len(path) == k:
            result.append(path[:])
            return
        
        # Pruning: need k - len(path) more elements
        # so stop when not enough elements remain
        remaining = k - len(path)
        for i in range(start, n - remaining + 2):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(1, [])
    return result

print(combine(4, 2))
# [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

Combination Sum (LC 39)

Find all combinations that sum to a target. Each number can be reused.

def combinationSum(candidates: list[int], target: int) -> list[list[int]]:
    result = []
    candidates.sort()
    
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break  # prune: sorted, so all future too large
            path.append(candidates[i])
            backtrack(i, path, remaining - candidates[i])  # i, not i+1 (reuse)
            path.pop()
    
    backtrack(0, [], target)
    return result

print(combinationSum([2, 3, 6, 7], 7))
# [[2,2,3], [7]]

Combination Sum II — No Reuse (LC 40)

def combinationSum2(candidates: list[int], target: int) -> list[list[int]]:
    candidates.sort()
    result = []
    
    def backtrack(start, path, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        
        for i in range(start, len(candidates)):
            if candidates[i] > remaining:
                break
            if i > start and candidates[i] == candidates[i - 1]:
                continue  # skip duplicates
            path.append(candidates[i])
            backtrack(i + 1, path, remaining - candidates[i])
            path.pop()
    
    backtrack(0, [], target)
    return result

print(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))
# [[1,1,6], [1,2,5], [1,7], [2,6]]

Pattern 3: Permutations

Permutations (LC 46)

Generate all permutations of distinct integers.

def permute(nums: list[int]) -> list[list[int]]:
    result = []
    
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False
    
    backtrack([], [False] * len(nums))
    return result

print(permute([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

// Java version
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    boolean[] used = new boolean[nums.length];
    backtrack(nums, used, new ArrayList<>(), result);
    return result;
}

private void backtrack(int[] nums, boolean[] used, List<Integer> path,
                       List<List<Integer>> result) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, used, path, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

Permutations II — With Duplicates (LC 47)

def permuteUnique(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    
    def backtrack(path, used):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            # Skip duplicate: same value, previous not used at this level
            if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
                continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False
    
    backtrack([], [False] * len(nums))
    return result

print(permuteUnique([1, 1, 2]))
# [[1,1,2], [1,2,1], [2,1,1]]

Pattern 4: Constraint Satisfaction

N-Queens (LC 51)

Place N queens on an NxN board so no two attack each other.

def solveNQueens(n: int) -> list[list[str]]:
    result = []
    cols = set()
    diag1 = set()  # row - col
    diag2 = set()  # row + col
    board = [['.' ] * n for _ in range(n)]
    
    def backtrack(row):
        if row == n:
            result.append([''.join(r) for r in board])
            return
        
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            
            # Place queen
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            
            backtrack(row + 1)
            
            # Remove queen
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)
    
    backtrack(0)
    return result

solutions = solveNQueens(4)
for sol in solutions:
    for row in sol:
        print(row)
    print()

Word Search (LC 79)

def exist(board: list[list[str]], word: str) -> bool:
    rows, cols = len(board), len(board[0])
    
    def backtrack(r, c, idx):
        if idx == len(word):
            return True
        if (r < 0 or r >= rows or c < 0 or c >= cols or
                board[r][c] != word[idx]):
            return False
        
        # Mark visited
        temp = board[r][c]
        board[r][c] = '#'
        
        # Explore all 4 directions
        found = (backtrack(r + 1, c, idx + 1) or
                 backtrack(r - 1, c, idx + 1) or
                 backtrack(r, c + 1, idx + 1) or
                 backtrack(r, c - 1, idx + 1))
        
        # Restore
        board[r][c] = temp
        return found
    
    for r in range(rows):
        for c in range(cols):
            if backtrack(r, c, 0):
                return True
    return False

Pattern Summary

Key Takeaways

Every backtracking problem follows the choose-explore-unchoose template. Subsets collect results at every node. Combinations collect results only when the path reaches the target length. Permutations consider all positions but skip used elements. Handle duplicates by sorting first and skipping elements that match the previous one at the same decision level. Pruning is what makes backtracking practical — without it, you are just generating all possibilities by brute force. Look for constraints that let you cut branches early.