Skip to main content
Talentd

Iterator for Combination - Solution & Explanation

MediumStringBacktrackingDesignIterator8 min readAsked at: Google
Practice this problem

Problem Statement

Design the CombinationIterator class:

  • CombinationIterator(string characters, int combinationLength) Initializes the object with a string characters of sorted distinct lowercase English letters and a number combinationLength as arguments.
  • next() Returns the next combination of length combinationLength in lexicographical order.
  • hasNext() Returns true if and only if there exists a next combination.

 

Example 1:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

 

Constraints:

  • 1 <= combinationLength <= characters.length <= 15
  • All the characters of characters are unique.
  • At most 104 calls will be made to next and hasNext.
  • It is guaranteed that all calls of the function next are valid.

Approach Overview

Problem Overview: Design an iterator that returns all combinations of length k from a given sorted string of characters. Each call to next() should return the next combination in lexicographical order, and hasNext() should indicate whether more combinations remain.

Approach 1: Precompute All Combinations (Time: O(C(n,k) * k), Space: O(C(n,k) * k))

This approach generates every valid combination during initialization using backtracking. Start from index 0, recursively build a string by choosing the next character and continuing until the length reaches k. Each completed combination is appended to a list. Because the input string is already sorted, the generated combinations naturally appear in lexicographic order. The iterator then simply maintains an index pointer: next() returns the current element and increments the pointer, while hasNext() checks whether the pointer is within bounds.

The main advantage is simplicity. Once the combinations are precomputed, each iterator call is constant time. The tradeoff is memory usage because all C(n,k) combinations are stored upfront.

Approach 2: Generate Combinations on the Fly (Time: O(C(n,k) * k), Space: O(k))

This approach generates the next combination only when needed instead of storing all results. Maintain an array of indices representing the current combination. Initially it contains [0,1,2,...,k-1]. When next() is called, build the string using those indices from the original characters.

To compute the next state, scan the indices from right to left and find the first position that can be incremented without exceeding its limit. Increase that index and reset all positions to its right to the smallest valid increasing sequence. This logic is similar to generating the next lexicographical combination and works well with an iterator design pattern. Only the current index array is stored, so the memory footprint stays small.

This technique avoids storing every combination and is typically preferred when the number of combinations is large. The time cost shifts from initialization to each call to next(), but each step still runs in about O(k).

Recommended for interviews: Interviewers usually expect the on‑the‑fly generation approach because it demonstrates understanding of string combination generation and iterator state management. Implementing the precomputation method first is still valuable because it proves you understand how combinations are formed. The optimized iterator version shows stronger design and algorithmic reasoning.

Approach 1: Precompute All Combinations

In this approach, we precompute all the combinations of the given string of a specified length. This allows us to provide the next combination in constant time by just iterating over the precomputed list. For this, we can use recursion or libraries to generate combinations initially and store them in an internal data structure.

To find all combinations of a particular length, you can use backtracking or an iterative process that resembles a binary-like increase in combinations selection.

This Python solution uses the itertools.combinations library to generate all the combinations of the given length at the initialization stage. Whenever next() is called, it returns the current combination and advances the index.

Code

PythonC++

Python

C++

Complexity

Time Complexity: O(n!) for precomputation, O(1) for next and hasNext.
Space Complexity: O(n!) due to storage of combinations.

Try this approach in the editor →

Approach 2: Generate Combinations on The Fly

Instead of generating all combinations at once, we can generate them on the fly when next() is called. This approach uses bit manipulation to generate the combination efficiently by representing each combination as a bitmask. However, this requires understanding how to generate valid combinations incrementally with proper bit manipulation.

This C# solution uses an indices array to represent the current combination. It simulates the generation of combinations by modifying the indices array with each call to next(). When there is a valid combination, the indices are updated to represent the next viable combination.

Code

C#JavaScript

C#

JavaScript

Complexity

Time Complexity: O(1) for next and hasNext, average complexity due to combination generation logic.
Space Complexity: O(combinationLength), the storage used for the indices.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Precompute All Combinations

Time Complexity: O(n!) for precomputation, O(1) for next and hasNext.
Space Complexity: O(n!) due to storage of combinations.

Generate Combinations on The Fly

Time Complexity: O(1) for next and hasNext, average complexity due to combination generation logic.
Space Complexity: O(combinationLength), the storage used for the indices.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Precompute All CombinationsO(C(n,k) * k)O(C(n,k) * k)When simplicity matters and memory is not a constraint
Generate Combinations on the FlyO(C(n,k) * k)O(k)When the number of combinations is large and memory should remain minimal

Video Solution

Iterator for combination | BitMasking | Backtracking | Leetcode #1286 • Techdose • 4,937 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Iterator for Combination easy or hard?
Iterator for Combination is rated Medium because it combines combination generation with object-oriented iterator design. The logic for computing the next lexicographic combination requires careful index manipulation.
Iterator for Combination Python/Java solution
In Python, combinations are often generated using backtracking with a list storing all results or with an index pointer for on-demand generation. Java implementations typically store indices in an int array and update them lexicographically to produce the next combination string.
How to solve Iterator for Combination in O(n)?
The full problem cannot be solved in O(n) overall because the iterator must eventually produce C(n,k) combinations. However, each call to next() can run in about O(k) time by updating the combination indices and rebuilding the string from the original characters.
What is the best approach for Iterator for Combination?
The most practical approach is generating combinations on the fly using a lexicographical index array. It stores only the current combination indices and updates them to produce the next combination. This keeps space complexity at O(k) while still generating all C(n,k) combinations in order.
Is Iterator for Combination asked at Google/Amazon/Meta?
Iterator and design-style problems like this frequently appear in interviews at large tech companies including Google, Amazon, and Meta. They test understanding of iterator patterns, combination generation, and maintaining internal state between calls.
What data structure is used in Iterator for Combination?
Most implementations use an array or list of indices to represent the current combination. Backtracking or iterative index updates generate the next combination while preserving lexicographic order.
What is the time complexity of Iterator for Combination?
Generating all combinations requires O(C(n,k) * k) time because each combination of length k must be constructed. In the precomputation approach this cost occurs during initialization, while in the iterator approach it is distributed across calls to next().

Ready to solve this problem?

Practice Iterator for Combination with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring