Domain 2MediumMEDIUM

Iterator for Combination

Pre-generates all valid combinations using backtracking during initialization and iterates through them with an index pointer for O(1) access time per call.

Domain: medium•Updated: 2026-09-14
#backtracking#list#lexicographical-order#iterator

Problem Breakdown

We need to implement a class that acts as an iterator over combinations of length combinationLength from the input string. The core requirements are maintaining state between calls (next() and hasNext()) and ensuring results follow lexicographical order. Since the input characters is guaranteed to be sorted, we can rely on Depth-First Search (DFS) traversal logic to generate combinations in the correct order naturally without additional sorting steps.

Intuition

  1. State Management: An iterator requires remembering where it left off. We use an index pointer (self.idx) pointing into a list of pre-computed results.
  2. Ordering Guarantee: Because characters is sorted and unique, iterating indices from 00 to N−1N-1 in our backtracking function ensures that combinations are generated lexicographically (e.g., ‘ab’ comes before ‘ac’).
  3. Pre-computation vs. Lazy Generation: While a true iterator might suggest generating the next combination on demand (O(1)O(1) space), doing so requires complex logic to find the “next” valid index configuration without backtracking every time. Given N≤15N \le 15, pre-generating all combinations fits easily in memory and simplifies next()/hasNext() to simple array access operations, which is often preferred for interview efficiency unless strict space constraints exist (which they don’t here).

Approach

  1. Initialization (__init__):
    • Initialize an empty list self.combinations.
    • Define a recursive helper function backtrack(start_index, current_path).
    • Base case: If path length equals combinationLength, join the characters and append to self.combinations.
    • Recursive step: Iterate through available indices starting from start_index to ensure unique combinations (no duplicates). Recurse with incremented index. Backtrack by popping after recursion returns.
  2. Next (next):
    • Retrieve the string at current self.idx.
    • Increment self.idx.
    • Return the retrieved combination.
  3. Has Next (hasNext):
    • Check if self.idx is within bounds of self.combinations.

Complexity Analysis

  • Time Complexity:
    • Initialization: O((NK)⋅K)O(\binom{N}{K} \cdot K), where we generate every valid combination and join characters (cost proportional to length). For N=15N=15, (157)=6435\binom{15}{7}=6435 combinations. This is negligible for modern hardware.
    • next(): O(K)O(K) due to string retrieval/copying, effectively amortized constant relative to input size constraints.
    • hasNext(): O(1)O(1).
  • Space Complexity:
    • Initialization: O((NK)⋅K)O(\binom{N}{K} \cdot K) to store the list of strings and recursion stack depth (O(N)O(N)). With max combinations ≈6435\approx 6435 and string length ≤15\le 15, memory usage is well within limits (typically < 20MB).

Solution

class CombinationIterator:
    def __init__(self, characters: str, combinationLength: int):
        self.combinations = []
        self.idx = 0
        
        # Helper function to generate combinations via backtracking
        # Since 'characters' is sorted and unique, DFS naturally yields lexicographical order.
        def backtrack(start_idx, current_path):
            if len(current_path) == combinationLength:
                self.combinations.append("".join(current_path))
                return
            
            for i in range(start_idx, len(characters)):
                # Add character to path and recurse with next index
                current_path.append(characters[i])
                backtrack(i + 1, current_path)
                current_path.pop() # Backtrack
        
        backtrack(0, [])

    def next(self):
        if self.idx < len(self.combinations):
            res = self.combinations[self.idx]
            self.idx += 1
            return res
    
    def hasNext(self):
        return self.idx < len(self.combinations)

Edge Cases Handled

  • Single Combination: If combinationLength equals the length of characters, only one combination exists. The logic correctly appends it once and returns false on subsequent checks via hasNext().
  • Full String Usage: Handles cases where we must use all characters (e.g., input “abc”, len 3).
  • Memory Constraints: Leverages Python’s list storage which is efficient enough for N≤15N \le 15, avoiding the complexity of implementing a custom iterator state machine that would be harder to debug in an interview setting.