Generating Unique Combinations

Hello! In our last lesson, we tackled permutations, where the order of elements is paramount. You learned to use a visited array within a backtracking structure to generate every possible arrangement of a set.

Today, we'll explore the related concept of combinations. While permutations are about arranging elements, combinations are about selecting them. The order of elements in a combination doesn't matter, so [1, 2] is the same as [2, 1]. This lesson will equip you with a powerful backtracking pattern to generate all unique combinations, even when the input data contains duplicates. Mastering this is a significant step, as combination problems are a classic in algorithmic interviews.

The Core Combination Pattern

Let's first establish how combinations differ from permutations and subsets.

• Subsets: Any selection of elements, including the empty set. Order doesn't matter. For [1, 2], subsets are [], [1], [2], [1, 2].
• Permutations: All possible orderings of all elements. For [1, 2], permutations are [1, 2] and [2, 1].
• Combinations: Subsets of a specific size k. For [1, 2, 3] and k=2, combinations are [1, 2], [1, 3], [2, 3].

The main challenge in generating combinations is to avoid producing different orderings of the same set of elements. How can we generate [1, 2] but prevent the redundant generation of [2, 1]?

The solution is to impose an artificial order on our choices. When we build a combination, we decide that once we've picked an element at index i, we will only consider elements from index i+1 onwards for the rest of that combination. This simple rule elegantly prevents us from ever "going back" to pick an earlier element, which is what creates different orderings of the same combination.

This is achieved by passing a startIndex to our recursive function. The video below provides an excellent visualization of this concept using a decision tree.

As you saw, the core of the backtracking logic becomes a loop that starts from the given startIndex and makes a recursive call with an updated index i + 1. This ensures we always move forward in the input array.

function backtrack(startIndex: number, currentCombination: number[]) {
  // Base case: if the combination is the right size, add it to results
  if (currentCombination.length === k) {
    result.push([...currentCombination]);
    return;
  }

  // Loop through candidates starting from startIndex
  for (let i = startIndex; i < candidates.length; i++) {
    // Choose
    currentCombination.push(candidates[i]);
    // Explore: next choice must come from i + 1 onwards
    backtrack(i + 1, currentCombination);
    // Unchoose (backtrack)
    currentCombination.pop();
  }
}

This startIndex strategy is the cornerstone of all combination-style backtracking problems.

Handling Duplicates in the Input

Now, let's address a common and important complication: what if the input array itself contains duplicates? Consider finding combinations from [1, 2, 2] that sum to 3. Using our current pattern, the recursive calls would explore:

1. Pick 1 (at index 0), then pick the first 2 (at index 1). We find [1, 2].
2. Backtrack, then pick 1 (at index 0), then pick the second 2 (at index 2). We find [1, 2] again.

This is a duplicate combination that we must eliminate. The standard solution involves two key steps:

1. Sort the input array. This places all duplicate elements next to each other (e.g., [1, 2, 2]).
2. Modify the loop logic. At any given level of recursion, once we've considered a number, we must skip over any of its immediate duplicates.

The rule can be stated as: in the loop that iterates from j = startIndex to the end, if j > startIndex and candidates[j] is the same as candidates[j-1], we skip candidates[j].

The condition j > startIndex is crucial. It means we only skip duplicates for the second choice and beyond at the current level of the decision tree. We always process the first occurrence of a number in a sequence of duplicates.

The following Algo.monster article provides a fantastic, in-depth explanation of this technique in the context of the "Combination Sum II" problem.

To visualize this process, consider the following recursion tree for finding combinations that sum to a target from an array with duplicates. Notice how many branches are pruned (marked with 'x') due to the duplicate-skipping logic.

Implementation and Common Pitfalls

Let's look at the complete TypeScript implementation from the Algo.monster article. It solves for a target sum, but the core logic for generating unique combinations is exactly what we've been discussing.

The logic you just read about—sorting the input and then conditionally skipping elements within the recursive loop—is the canonical pattern for this class of problems.

The following video also provides a walkthrough in JavaScript, which may help solidify your understanding of the implementation details.

Conclusion

In this lesson, you've added another crucial backtracking pattern to your toolkit. You've seen how a simple change in the recursive call—passing an index—can solve the complex problem of generating unique combinations.

Key Takeaways:

• Combinations vs. Permutations: Combinations are unordered selections. To prevent generating different orderings of the same combination (like [1, 2] and [2, 1]), we enforce an order on our choices.
• The startIndex Pattern: By passing a startIndex to the recursive function and making the next recursive call with i + 1, we ensure that our selections always move forward through the input array.
• Handling Duplicate Inputs: To avoid generating identical combinations from duplicate numbers in the input, we first sort the array. Then, within our recursive helper's loop, we add a condition to skip over any duplicate element that is not the first in a sequence at that level of recursion.
• The Full Pattern: The robust solution for generating unique combinations from an array that may contain duplicates is: Sort + Backtrack with startIndex + Skip duplicates.

In our next lesson, we will focus more deeply on the concept of pruning. While we've seen some implicit pruning today (e.g., stopping if the sum exceeds the target), we'll explore how to use constraints to cut off entire branches of the search tree even earlier, making our backtracking algorithms much more efficient.