Generating Combinations and Subsets with Backtracking

1. Generating All Subsets (The Power Set)

The "power set" of a set is the collection of all its possible subsets, including the empty set and the set itself. For an input array like [1, 2, 3], we want to generate:
[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]

Visualizing the Decision Tree

The core idea for generating subsets is simpler than for permutations. For each element in the input array, we face a binary choice:

1. Include the element in our current subset.
2. Exclude the element from our current subset.

If we make a decision for every element, we will have formed one complete, unique subset. To find all subsets, we just need to explore every possible sequence of these choices. This forms a decision tree where each level corresponds to an element, and each branch represents the "include" or "exclude" choice.

This diagram illustrates the decision process. Starting with an empty set, we decide for '1' (include/exclude), then for '2', and finally for '3', tracing all paths to find every subset.

The Backtracking Algorithm in Action

Let's see how this "include vs. exclude" logic translates into code using our backtracking template. The following video provides an excellent walkthrough.

As the video explains, our recursive backtracking function will explore these two paths. This leads to a common and elegant implementation pattern.

Code Implementation and Key Differences

Here is a common implementation for the subsets problem. Notice how it differs from the permutations code you saw in the last lesson.

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

    def backtrack(index):
        # BASE CASE: When we have considered all numbers, we have a valid subset.
        if index >= len(nums):
            # Add a *copy* of the current subset to our results.
            result.append(current_subset[:])
            return

        # ---- The Two Choices ----

        # CHOICE 1: Include the element nums[index]
        # 1. Choose
        current_subset.append(nums[index])
        # 2. Explore
        backtrack(index + 1)
        # 3. Un-choose (backtrack)
        current_subset.pop()

        # CHOICE 2: Exclude the element nums[index]
        # We simply move to the next index without adding the element.
        backtrack(index + 1)

    backtrack(0)
    return result

# Example:
print(subsets([1, 2, 3]))
# Output: [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]
# (Note: the order of subsets in the output may vary)

Key Differences from Permutations:

• No used array: In permutations, we needed a used array because we could pick any unused element at any position. Here, to avoid duplicates (since order doesn't matter) and ensure we only consider each element once per path, we simply advance an index. The decision is only about nums[index], and then we move on to nums[index + 1].
• Two Recursive Calls: The "include" and "exclude" choices are often modeled as two separate recursive calls within the function body. The "include" path performs the full "Choose-Explore-Unchoose" cycle, while the "exclude" path is just a simple "Explore" step on the next index.

2. Generating Combinations of Size k

Now, what if you're asked not for all subsets, but only for subsets of a specific size, k? This is a combinations problem. For example, find all combinations of size 2 from [1, 2, 3]. The answer would be [[1, 2], [1, 3], [2, 3]].

This is a minor but important variation of the subsets problem. We can use a very similar backtracking structure. The main change is in our base case. Instead of adding a path when we've considered all elements, we add it only when our current path reaches the desired length k.

The following video snippet demonstrates this simple but powerful modification.

A More Standard Combination Implementation

While the "include/exclude" pattern works for combinations, a more common and intuitive approach for combinations uses a single recursive path with a for loop, similar to the structure we first saw for subsets in the previous module. This approach is easier to reason about when it comes to pruning.

def combine(nums, k):
    result = []
    current_combination = []

    def backtrack(start_index):
        # BASE CASE: If the combination is the desired size, add it to results.
        if len(current_combination) == k:
            result.append(current_combination[:])
            return
        
        # If we can't possibly reach size k anymore, stop. (Pruning)
        if len(current_combination) + (len(nums) - start_index) < k:
            return

        # Iterate through the available choices
        for i in range(start_index, len(nums)):
            # 1. Choose
            current_combination.append(nums[i])
            # 2. Explore
            backtrack(i + 1) # Move to the next start index to avoid re-using elements
            # 3. Un-choose
            current_combination.pop()

    backtrack(0)
    return result

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

This structure is very powerful. The start_index and the recursive call backtrack(i + 1) are what prevent us from generating permutations or using the same element twice. By starting the loop at start_index and passing i + 1 to the next call, we ensure that once we've used nums[i], we will only consider elements that appear after it in the array.

3. Complexity Analysis

For your competitive programming journey, understanding complexity is non-negotiable.

• Subsets (Power Set):

  • Time Complexity: O(n * 2^n). There are 2^n possible subsets. For each subset, we perform a copy operation, which can take up to O(n) time.
  • Space Complexity: O(n). The depth of the recursion is n, which determines the space used by the call stack and the current_subset list.

• Combinations (of size k):

  • Time Complexity: O(k * C(n, k)), where C(n, k) is "n choose k", the number of combinations. We generate C(n, k) combinations, and each copy takes O(k) time.
  • Space Complexity: O(k) or O(n) depending on the implementation. The recursion depth is at most k in the second implementation, but can be n in the first.

You can review the detailed complexity analysis for the subsets problem in the Algo.monster article under the "Time and Space Complexity" section (LINK, section 5).

Conclusion

In this lesson, you've mastered how to apply the backtracking template to generate subsets and combinations. This solidifies your understanding of how to manage choices and constraints in problems where order does not matter.

Key Takeaways:

• Subsets vs. Permutations: The key difference is that for subsets/combinations, order doesn't matter. This is handled algorithmically by using a start_index to ensure we only move forward through the input array, preventing duplicates like {1, 2} and {2, 1}.
• Two Patterns for Subsets: You saw two valid patterns: the "include/exclude" model with two recursive calls, and the for loop model with a start_index. Both are effective ways to explore the decision tree.
• Combinations as a Variation: Generating combinations of size k is a direct extension of generating subsets, typically involving a modified base case and potential for pruning.

Up Next:
We will move on to a different class of backtracking problems: constraint satisfaction problems. Our next lesson will tackle the famous N-Queens problem. Instead of just generating all possibilities, you'll learn how to use constraints to aggressively "prune" the decision tree, discarding invalid paths early. This is a crucial skill for solving many complex algorithmic puzzles.