Backtracking for Combinatorial Generation

1. Generating Subsets: The "Include or Exclude" Pattern

We touched upon the Subsets problem (LeetCode 78) in our last lesson as a way to introduce the backtracking template. Let's now do a deep dive to solidify your understanding. The problem is: given an integer array nums of unique elements, return all possible subsets (the power set).

For each element in nums, we have a binary choice: either we include it in our current subset, or we exclude it. By systematically exploring every one of these choices for every element, we can generate all 2^N possible subsets.

To see this in action, let's watch a detailed walkthrough.

As the video explains, there are two common ways to structure the backtracking recursion for subsets. Let's look at the implementation that more closely follows the "looping through choices" model we discussed previously.

def subsets(nums):
    result = []
    path = []

    def backtrack(start_index):
        # Add a copy of the current path. In this pattern, every node in the
        # decision tree represents a valid subset.
        result.append(list(path))

        # Explore further options by adding subsequent elements.
        for i in range(start_index, len(nums)):
            # 1. Choose: Add the element nums[i]
            path.append(nums[i])
            
            # 2. Explore: Recurse, starting from the *next* index to avoid duplicates
            # like [1, 2] and [2, 1] if order doesn't matter.
            backtrack(i + 1)
            
            # 3. Unchoose: Backtrack by removing the element.
            path.pop()

    backtrack(0)
    return result

# Example:
print(subsets([1, 2, 3]))
# Output: [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

A crucial detail here is the backtrack(i + 1) call. By starting the next exploration at i + 1, we ensure that we only consider elements that appear after the current one, which elegantly prevents us from generating duplicate combinations (e.g., after considering [1, 2], we won't later consider [2, 1]).

2. Generating Combinations: Subsets of a Fixed Size

The "Combinations" problem (LeetCode 77) is a direct variation of Subsets. The prompt is: given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

This is essentially a Subsets problem with an added constraint: we are only interested in subsets of a specific size, k. We can adapt our previous template with a very minor change.

The core idea is to modify the base case. Instead of adding our path to the results at every step, we only add it when its length is exactly k.

Here's the code. Notice how similar it is to our subsets implementation.

def combine(n, k):
    result = []
    path = []
    nums = list(range(1, n + 1)) # The numbers to choose from are [1, 2, ..., n]

    def backtrack(start_index):
        # Base Case: If we have a combination of size k, we've found a solution.
        if len(path) == k:
            result.append(list(path))
            return # Stop this path, as adding more elements would exceed size k.

        # If there are not enough numbers left to form a combination of size k,
        # we can prune this branch. This is a common optimization.
        if len(path) + (n - start_index + 1) < k:
            return

        # Explore further options.
        for i in range(start_index, len(nums)):
            # 1. Choose
            path.append(nums[i])
            # 2. Explore
            backtrack(i + 1)
            # 3. Unchoose
            path.pop()
    
    backtrack(0)
    return result

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

3. Generating Permutations: When Order Matters

Permutations (LeetCode 46) present a different challenge. The prompt: given an array nums of distinct integers, return all possible permutations.

In a permutation, [1, 2, 3] is different from [3, 2, 1]. The key distinctions from subsets/combinations are:

1. Order matters.
2. All elements from the input must be used exactly once in each permutation.

Because we might need to pick the number 3 before the number 1, the start_index trick from before won't work. We need a different way to keep track of which elements have already been included in our current path to avoid using them again. The most common method is a visited boolean array or a hash set.

The core logic changes from "don't pick elements before start_index" to "don't pick any element that is currently in use."

Here is a Python implementation based on this pattern:

def permute(nums):
    result = []
    path = []
    # A boolean array to mark which elements have been used in the current path.
    used = [False] * len(nums)

    def backtrack():
        # Base Case: If the path length equals the input length, we have a full permutation.
        if len(path) == len(nums):
            result.append(list(path))
            return

        # Explore all numbers in every recursive call.
        for i in range(len(nums)):
            # Constraint: Only proceed if the number at index i has NOT been used.
            if used[i]:
                continue
            
            # 1. Choose: Mark as used and add to path.
            used[i] = True
            path.append(nums[i])
            
            # 2. Explore: Recurse.
            backtrack()
            
            # 3. Unchoose: Un-mark and remove from path to backtrack.
            used[i] = False
            path.pop()

    backtrack()
    return result

# Example:
print(permute([1, 2, 3]))
# Output: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

4. Unifying the Patterns: A Summary

You've now seen how one core template adapts to solve three distinct problems. For interviews, being able to articulate why you're making a specific implementation choice is critical. Let's consolidate the key differences.

The choice between backtrack(i + 1) and backtrack() with a used array is the most fundamental distinction.

• i + 1 (For Subsets/Combinations): This implies a linear, forward-only exploration. Once you've decided on element i, you never look back at elements 0 through i-1. This is perfect when order doesn't matter.
• used array (For Permutations): This allows the exploration to pick any available element from the entire original set at any point. This is necessary when order matters.

The following cheat sheet provides an excellent summary of these patterns and is a great resource to save for future review.

Conclusion

Mastering these three fundamental patterns—Subsets, Combinations, and Permutations—provides a solid foundation for almost any backtracking problem you'll face. The true skill lies not just in writing the code, but in quickly identifying the constraints of the problem and choosing the right state management technique.

Key Takeaways:

• Subsets and Combinations are similar. They both solve problems where order does not matter and use a start_index passed as i + 1 in the recursive call to prevent duplicate combinations.
• Permutations solve problems where order matters. They require tracking used elements, typically with a visited boolean array, allowing any unused element to be chosen at any step.
• Problems allowing element reuse (like Combination Sum) modify the recursive call to backtrack(i), allowing the same element to be considered again.

In our next lesson, we will move from generating combinatorial sets to solving a famous constraint satisfaction problem: the N-Queens puzzle. This will require you to expand the backtracking template to handle more complex rules and state validation.