Introduction

Backtracking is a general algorithmic technique that tries to find a solution to a problem by incrementally building candidates and abandoning a candidate ("backtracking") as soon as it determines that the candidate cannot possibly be completed to a valid solution. Below we explore five common variants frequently encountered in coding interviews.

Backtracking Problem Variants

1. Permutations with Duplicates

Modified Template Variation: Generate all permutations of a list where elements may repeat. The standard backtracking template for permutations is modified to handle duplicates.

Differences from Base: We sort the input list and use a boolean used[] array to mark elements already in the current permutation. Before recursing on an element, we check if it’s a duplicate of a previous element that hasn’t been used yet – if so, we skip it. This pruning avoids generating duplicate permutation sequences.

Additional Logic: Each recursion level represents fixing one position in the permutation. We loop over all numbers and choose any not yet used. Skip any number if it is the same as the immediately previous number and that previous number was not used. We backtrack by un-marking the element as unused after exploring that branch.

Example – LeetCode 47: Permutations II

Problem: Given a collection of numbers that might contain duplicates, return all possible unique permutations. For example, input [1,1,2] should produce output [[1,1,2], [1,2,1], [2,1,1]].

Code (Python):

def permuteUnique(nums):
    nums.sort()  # Sort to enable duplicate skipping
    used = [False] * len(nums)
    results = []
    def backtrack(path):
        if len(path) == len(nums):
            results.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]:
                continue  # already used
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue  # skip duplicates
            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False
    backtrack([])
    return results

2. Combination Sum (with No Repeats)

Modified Template Variation: Find combinations of numbers that sum to a target, where each number can be used at most once. This is a constrained combination generation problem (Combination Sum II).

Differences from Base: We have a target sum constraint and cannot reuse the same candidate number multiple times. Sort candidates and use recursion with an index to ensure each number is taken once. Prune if sum exceeds target or next candidate > remaining target.

Duplicate Handling: Candidate list may have duplicates, but results must be unique. After sorting, skip duplicate candidates in the loop (if i > start and candidates[i] == candidates[i-1]).

Example – LeetCode 40: Combination Sum II

Problem: Given candidates and target, find unique combinations summing to target. Each number used once. E.g., candidates = [10,1,2,7,6,1,5], target = 8 yields [[1,1,6],[1,2,5],[1,7],[2,6]].

Code (Python):

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

3. Palindrome Partitioning

Modified Template Variation: Partition a string into all possible substrings such that each substring is a palindrome.

Differences from Base: Iterate over possible substring end indices. A crucial addition is a palindrome check for pruning.

Backtracking Approach: At a given start index, try to cut string at end index i >= start. If s[start:i+1] is palindrome, include it and recurse for remainder from i+1.

Example – LeetCode 131: Palindrome Partitioning

Problem: Given string s, partition s into palindromic substrings. E.g., s = "aab" -> [["a","a","b"], ["aa","b"]].

Code (Python):

def partition(s: str):
    res = []
    part = []
    def is_palindrome(sub):
        return sub == sub[::-1]
    def backtrack(start):
        if start == len(s):
            res.append(part.copy())
            return
        for i in range(start, len(s)):
            if is_palindrome(s[start:i+1]):
                part.append(s[start:i+1])
                backtrack(i+1)
                part.pop()
    backtrack(0)
    return res

4. N-Queens

Modified Template Variation: Place n queens on an n x n chessboard so no two queens threaten each other.

Differences from Base: Constructing an n x n grid configuration. Place queens row by row. Choices are columns in current row.

Pruning with Constraints: Check safety: no other queen in column or diagonals. Use sets for occupied columns/diagonals (diag1 = r+c, diag2 = r-c).

Example – LeetCode 51: N-Queens

Problem: Given n, return all distinct solutions. For n = 4, solutions include [".Q..", "...Q", "Q...", "..Q."].

Code (Python):

def solveNQueens(n: int):
    results = []
    cols = set()
    posDiag = set()  # r+c
    negDiag = set()  # r-c
    board = [["."] * n for _ in range(n)]
    
    def backtrack(r: int):
        if r == n:
            solution = ["".join(row) for row in board]
            results.append(solution)
            return
        for c in range(n):
            if c in cols or (r+c) in posDiag or (r-c) in negDiag:
                continue
            board[r][c] = "Q"
            cols.add(c); posDiag.add(r+c); negDiag.add(r-c)
            backtrack(r+1)
            board[r][c] = "."
            cols.remove(c); posDiag.remove(r+c); negDiag.remove(r-c)
    backtrack(0)
    return results

5. Generate Parentheses

Modified Template Variation: Generate all combinations of n pairs of parentheses that are valid (well-formed).

Differences from Base: Use two counters (open_count, close_count). Add '(' if open_count < n. Add ')' if close_count < open_count.

Backtracking Approach: Start with empty string. Recursively try adding '(' or ')' based on rules. Base case: open_count == close_count == n.

Example – LeetCode 22: Generate Parentheses

Problem: Given n pairs, generate all well-formed parentheses. E.g., n = 3 -> ["((()))","(()())", ... ].

Code (Python):

def generateParenthesis(n: int):
    res = []
    def backtrack(open_count, close_count, current_str): # Renamed current to current_str
        if open_count == close_count == n:
            res.append(current_str)
            return
        if open_count < n:
            backtrack(open_count+1, close_count, current_str + "(")
        if close_count < open_count:
            backtrack(open_count, close_count+1, current_str + ")")
    backtrack(0, 0, "")
    return res

Interactive Backtracking Animations

References

The above patterns and examples are distilled from common LeetCode interview questions and solutions. Mastering these backtracking patterns (permutations, combinations, partitioning, constraint satisfaction, and balanced generation) provides a strong foundation for tackling a wide range of problems commonly asked in interviews.