Iterator for Combination: Design Meets Backtracking

Design a CombinationIterator class that receives a string of sorted distinct lowercase characters and a combination length. It should support two operations: next() returns the next combination in lexicographic order, and hasNext() returns whether there is still a combination left to return.

This is LeetCode 1286: Iterator for Combination, and it sits at the intersection of two patterns. On one side you have the combination-generation technique from Combinations. On the other side you have the iterator design pattern, which you may have seen in Binary Search Tree Iterator. The trick is that once you know how to generate combinations in sorted order, the iterator part becomes almost trivial.

For characters = "abc" and combinationLength = 2, the iterator should produce "ab", "ac", "bc" in that order.

Why this problem matters

Iterator problems test whether you can separate the logic of generating results from the logic of serving them. In a real codebase, you would not dump every combination into memory up front if the caller might only need the first few. But for an interview setting, the pre-generation approach is clean, correct, and easy to reason about. It also lets you practice the combination-generation backtracking pattern without getting tangled in on-the-fly state management.

If you already know how to generate combinations from Combinations or Subsets, this problem is a chance to wrap that skill in a class interface. If you do not know the combination pattern yet, this is a good reason to learn it, because it shows up in a concrete design context rather than a standalone enumeration problem.

The key insight

Since the input characters are already sorted, any backtracking approach that picks characters left to right will naturally produce combinations in lexicographic order. That means you can pre-generate all combinations in the constructor, store them in a list, and keep an integer pointer to track which one to return next.

The algorithm:

1. In __init__, run a standard backtracking routine that picks combinationLength characters from characters, always moving the start index forward. Store every completed combination in a list.
2. Initialize a pointer self.idx = 0.
3. next() returns self.combos[self.idx] and increments self.idx.
4. hasNext() returns self.idx < len(self.combos).

The backtracking is the same choose-explore-unchoose skeleton you use for Combinations. The only difference is that you are picking characters from a string instead of numbers from a range, and you join the picked characters into a string before storing them.

The solution

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.combos = []
        self.idx = 0

        def backtrack(start, path):
            if len(path) == combinationLength:
                self.combos.append("".join(path))
                return
            for i in range(start, len(characters)):
                path.append(characters[i])
                backtrack(i + 1, path)
                path.pop()

        backtrack(0, [])

    def next(self) -> str:
        result = self.combos[self.idx]
        self.idx += 1
        return result

    def hasNext(self) -> bool:
        return self.idx < len(self.combos)

Let's walk through the pieces.

The constructor calls backtrack(0, []). At each level, you iterate over characters starting from index start. You append the character at index i, recurse with start = i + 1 to avoid reusing earlier characters, and then pop it off. When the path reaches combinationLength, you join the characters into a string and add it to self.combos.

Because characters is already sorted and you always pick characters in left-to-right order, the generated list is automatically in lexicographic order. No sorting step needed.

The next() method simply grabs the combination at the current pointer and bumps the pointer forward. hasNext() checks whether the pointer is still within the bounds of the list.

Visual walkthrough

Let's trace how the iterator works with characters = "abc" and combinationLength = 2. The constructor generates all three combinations, and then the caller uses next() and hasNext() to consume them.

The pointer does all the work. Each next() call is O(1) because it just reads from a list. The expensive part, generating the combinations, happens once in the constructor.

Complexity analysis

Constructor time is O(k * C(n, k)), where n is the length of characters and k is combinationLength. There are C(n, k) combinations, and each one takes O(k) time to build the string.

Constructor space is O(k * C(n, k)) to store all combinations. Each combination is a string of length k.

next() and hasNext() are both O(1) per call. They just read from the list and compare an index.

The building blocks

This problem is built on three reusable pieces that CodeBricks drills independently.

Combination generation via backtracking

The core of the constructor is the same backtracking skeleton from Combinations:

def backtrack(start, path):
    if len(path) == k:
        result.append(path[:])
        return
    for i in range(start, n):
        path.append(items[i])
        backtrack(i + 1, path)
        path.pop()

This pattern shows up whenever you need all ways to choose k items from n without repetition. The start-index parameter ensures you pick items in order and never produce duplicates. You will see the same skeleton in Combination Sum, Subsets, and Letter Tile Possibilities.

Lexicographic ordering from sorted input

When the input is sorted and you pick items left to right, the output is automatically in lexicographic order. This is a property of the backtracking approach, not something you need to add. It matters here because the problem explicitly requires sorted output, and knowing that it comes for free means you do not need a separate sort step.

Iterator design pattern

Wrapping a pre-computed list with an index pointer is the simplest iterator pattern. The pointer tracks consumption state. next() returns and advances. hasNext() checks bounds. This same pattern appears in Binary Search Tree Iterator, where you flatten an in-order traversal into a list (or use a stack for lazy evaluation).

Edge cases

Before submitting, check these:

• combinationLength equals len(characters): Only one combination exists, which is the entire string. The iterator should return it once, then hasNext() returns false.
• combinationLength equals 1: Every single character is its own combination. The iterator returns each character in order.
• Single character string: If characters = "a" and combinationLength = 1, the iterator returns "a" once.
• Maximum constraints: With characters of length 15 and combinationLength = 8, there are C(15, 8) = 6435 combinations. The pre-generation approach handles this easily.
• Calling next() without checking hasNext(): The problem guarantees all calls are valid, so you do not need to handle out-of-bounds. But in production code, you would want a guard.

From understanding to recall

You understand how backtracking generates combinations in sorted order. You see how the pointer-based iterator wraps the list. But can you implement the full class, including the backtracking constructor, from memory in under three minutes?

That is the gap between understanding and interview performance. The combination-generation backtracking skeleton is one pattern. The iterator wrapper is another. Independently, each is simple. But under time pressure, you need both to flow automatically.

Spaced repetition closes the gap. You practice writing the backtracking skeleton, then wrapping it in the iterator class, at increasing intervals. After a few rounds, you see "iterator for combination" and the full class structure appears in your mind without conscious effort.

The combination-generation pattern and the iterator pattern are two of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Combinations - The pure combination-generation problem. The backtracking skeleton in the constructor of this problem is identical to the solution for Combinations.
• Subsets - Uses the same choose-explore-unchoose pattern without a size constraint. Every node is a valid result. Compare with Combinations, where only leaves at depth k are valid.
• Letter Tile Possibilities - Another backtracking enumeration problem that counts distinct sequences. Shows how the same skeleton adapts to different counting and uniqueness constraints.

CodeBricks breaks Iterator for Combination into its combination-generation and iterator building blocks, then drills each one independently with spaced repetition. You type the backtracking skeleton from scratch until it is automatic, then layer on the class interface. When a design-plus-backtracking problem shows up in your interview, you do not think about it. You just write it.