Analyzing Backtracking Complexity: Subsets, Combinations, and Permutations

Hello! Over the past few lessons, we've built a solid foundation in backtracking by implementing algorithms to generate subsets, combinations, and permutations. We've focused on the "how"—the code, the recursion, and handling tricky cases like duplicates. Now, we'll shift our focus to the "what"—what is the performance cost of these algorithms?

This lesson will equip you to estimate the time complexity of backtracking solutions for subsets, combinations, and permutations. This is a critical skill for coding interviews, where you're often asked to analyze your own solution. We'll develop a practical framework for this estimation, focusing on intuition and the structure of the recursion tree, rather than complex mathematical proofs, which aligns with your goal of gaining a deep but practical understanding.

A General Framework for Analyzing Backtracking

At its core, a backtracking algorithm explores a tree of choices. To estimate its time complexity, we need to understand two things: the size of this tree and the amount of work we do at each step.

A good rule of thumb for estimating the time complexity is:

Time Complexity ≈ (Number of states/nodes in the recursion tree) × (Work done per state/node)

For many problems, the total number of leaf nodes in the tree corresponds to the number of valid solutions. The work done to generate the final list of solutions often dominates the complexity. A more refined estimate is:

Time Complexity ≈ (Number of valid solutions) × (Work to build one solution) + (Work in all non-solution nodes)

Let's apply this framework to the problems we've studied.

Case 1: Subsets (Power Set)

Recall the "subsets" problem where we generate all possible subsets of a given set [1, 2, 3]. The fundamental choice for each element is binary: either we include it in the current subset, or we exclude it.

• Recursion Tree: For an input of size $n$, this creates a binary decision tree of depth $n$.
• Number of Solutions (Leaves): Since each of the $n$ elements can either be in or out of a subset, there are $2\times 2\times ...\times 2=2^n$ possible subsets. These are the leaf nodes of our conceptual decision tree.
• Work per Solution: When our backtracking function reaches a leaf (a complete subset), we typically copy the temporary list holding the current subset into our final results list. The maximum length of a subset is $n$, so this copy operation takes up to $O(n)$ time.

Putting It Together:
The total work is dominated by generating and storing all the subsets. We have $2^n$ subsets in total. While some are short (like the empty set) and some are long (the set itself), the total number of elements across all subsets is $n\cdot 2^{n-1}$. Therefore, the time complexity to generate all results is $O(n\cdot 2^n)$.

The following resource provides a great walkthrough of this estimation.

The NeetCode video on subsets also touches upon this, reinforcing the final complexity.

Space Complexity: The space complexity is also dominated by storing the output, which is $O(n\cdot 2^n)$. The recursion stack depth contributes an additional $O(n)$, but this is overshadowed by the output size.

Case 2: Permutations

For permutations of a set of size $n$, the choice structure is different.

• Recursion Tree: At the first level of recursion, we have $n$ choices for the first element. At the second level, we have $n-1$ choices, and so on, until we have only one choice for the last element.
• Number of Solutions (Leaves): The total number of permutations is $n\times (n-1)\times ...\times 1=n!$. These are the leaf nodes of our recursion tree.
• Work per Solution: Each time we form a complete permutation of length $n$, we copy it to our results list. This is an $O(n)$ operation.

Putting It Together:
Since we generate $n!$ solutions and each requires an $O(n)$ copy, the time complexity is $O(n\cdot n!)$. The number of internal nodes in the permutation recursion tree is also on the order of $O(n!)$, so this estimate holds.

The following video provides an excellent visual and verbal explanation of where this complexity comes from.

Space Complexity: Similar to subsets, the space is dominated by the output, which requires storing $n!$ permutations of length $n$, leading to $O(n\cdot n!)$ space. The recursion stack adds $O(n)$.

Case 3: Combinations (n choose k)

Finally, let's consider generating all combinations of size k from a set of n elements (the "n choose k" problem).

• Recursion Tree: This tree is pruned compared to the subsets tree. The recursion stops once our current combination reaches size k. The depth of the recursion is k.
• Number of Solutions (Leaves): The number of ways to choose k elements from a set of n is given by the binomial coefficient, $C(n,k)=\frac{n!}{k!(n-k)!}$. This is the number of leaf nodes.
• Work per Solution: Each time we form a valid combination of size k, we perform an $O(k)$ copy operation.

Putting It Together:
The time complexity is the number of solutions multiplied by the work to copy each one: $O(C(n,k)\cdot k)$.

This is cleanly summarized in the following reading.

Space Complexity: Storing the output requires $O(C(n,k)\cdot k)$ space. The recursion stack depth is $O(k)$ or $O(n)$ depending on the specific implementation.

A Visual Summary and the Power of Pruning

The "Backtracking Patterns Cheat Sheet" below provides a great visual summary of the recursion trees for these problems.

Let's interpret this sheet in light of what we've learned:

• Subset Pattern: Shows the "pick/not pick" tree, leading to $O(2^n)$ solutions. As we analyzed, the runtime including output is $O(n\cdot 2^n)$. The sheet simplifies this, which is common.
• Permutation Pattern: Shows the tree with a decreasing number of branches ($n,n-1,...$), correctly identifying the $O(n!)$ nature.
• Combination Pattern: This depicts generating combinations by iterating through choices ([1], then [1,2], [1,3]). If this process is used to generate combinations of all possible sizes, it becomes equivalent to the subsets problem, hence the $O(2^n)$ complexity listed. This is different from the specific "n choose k" problem we analyzed. It's a good reminder that the problem definition is key!
• Combination Sum Pattern: This hints at a more advanced type of problem. The key takeaway is the concept of pruning. A backtracking algorithm's actual performance is often better than the theoretical worst-case because invalid paths are abandoned early.

The image below shows a pruned search tree for a Combination Sum problem. Notice how the red arrows indicate branches that were "pruned" or abandoned because they could not possibly lead to a solution. This is the essence of the "constraint" in the backtracking framework (choices, constraints, goal) and is what makes backtracking more efficient than brute-forcing every single possibility.

Conclusion

In this lesson, we transitioned from implementing backtracking algorithms to analyzing their performance. This is the final step in truly mastering an algorithmic pattern.

Key Takeaways:

• General Estimation Strategy: The time complexity of a backtracking algorithm is strongly related to the number of solutions and the cost of building each one.
• Subsets (Power Set): With $n$ elements, you have $2^n$ subsets. The time complexity is $O(n\cdot 2^n)$ due to copying results.
• Permutations: You have $n!$ permutations. The time complexity is $O(n\cdot n!)$.
• Combinations (n choose k): You have $C(n,k)$ combinations. The time complexity is $O(C(n,k)\cdot k)$.
• Complexity Classes: Notice the hierarchy of growth: $O(C(n,k)\cdot k)$ can be much smaller than $O(n\cdot 2^n)$, which in turn is much smaller than $O(n\cdot n!)$ for larger $n$.

This lesson concludes our module on backtracking. You are now equipped not only to implement these core patterns but also to analyze their efficiency confidently.

In the next module, we will explore a new data structure: the Trie, or prefix tree. We will see how it can be used to solve string-related problems efficiently, and interestingly, how it can be combined with backtracking to dramatically prune the search space in problems like finding words on a grid.