# Iterator for Combination
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/iterator-for-combination)
Canonical: https://scaleengineer.com/dsa/problems/iterator-for-combination
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking), [Design](https://scaleengineer.com/dsa/patterns/design), [Iterator](https://scaleengineer.com/dsa/patterns/iterator)
**Data structures:** String
---
## Problem
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.

# Approaches
## Approach 1: Pre-computation using Backtracking
This approach involves generating all possible combinations of the specified length during the initialization of the iterator. These combinations are then stored in a data structure, like a list or a queue. The `next()` and `hasNext()` methods then simply operate on this pre-computed list.
**Time:** Constructor: `O(C(N, K) * K)`. We generate `C(N, K)` combinations, and creating each string takes `O(K)` time.
`next()`: `O(1)`.
`hasNext()`: `O(1)`. · **Space:** O(C(N, K) * K), where N is the length of `characters` and K is `combinationLength`. This is required to store all `C(N, K)` combinations, each of length K.
**Pros:** `next()` and `hasNext()` operations are very fast (O(1) time complexity).; The logic for `next()` and `hasNext()` is extremely simple once the combinations are generated.
**Cons:** High upfront computational cost in the constructor. The iterator might be slow to initialize if the number of combinations is large.; High memory usage, as all combinations must be stored in memory. This is not scalable for larger inputs.; Inefficient if the iterator is created but only a few elements are consumed, as all the work is done upfront.
### Explanation
The core of this approach is a recursive backtracking function that generates all combinations. In the `CombinationIterator` constructor, we initialize an empty list to store the results and then call a recursive helper function, `generate(startIndex, currentCombination)`. This function explores all possible combinations: if the current combination reaches the desired length, it's added to our list. Otherwise, it iterates through the remaining characters, adding each one and making a recursive call. Since the input `characters` string is sorted and our exploration is sequential, the combinations are naturally generated in lexicographical order. The `next()` method then simply returns the next element from the pre-computed list, and `hasNext()` checks if we've reached the end of the list.

```java
import java.util.ArrayList;
import java.util.List;

class CombinationIterator {
    private List<String> combinations;
    private int index;

    public CombinationIterator(String characters, int combinationLength) {
        this.combinations = new ArrayList<>();
        this.index = 0;
        generateCombinations(characters, combinationLength, 0, new StringBuilder());
    }

    private void generateCombinations(String characters, int combinationLength, int start, StringBuilder sb) {
        if (sb.length() == combinationLength) {
            combinations.add(sb.toString());
            return;
        }
        for (int i = start; i < characters.length(); i++) {
            sb.append(characters.charAt(i));
            generateCombinations(characters, combinationLength, i + 1, sb);
            sb.deleteCharAt(sb.length() - 1); // backtrack
        }
    }

    public String next() {
        return combinations.get(index++);
    }

    public boolean hasNext() {
        return index < combinations.size();
    }
}
```
### Algorithm
- `CombinationIterator(characters, combinationLength)`:
    1. Initialize an empty list `combinations` to store the generated combination strings.
    2. Initialize a pointer `currentIndex = 0` to track the position in the list.
    3. Define a recursive helper function, `backtrack(start, currentStringBuilder)`.
    4. Call the initial helper function: `backtrack(0, new StringBuilder())`.
- `backtrack(start, currentStringBuilder)` function:
    1. **Base Case:** If `currentStringBuilder.length()` equals `combinationLength`, a valid combination has been formed. Add its string representation to the `combinations` list and return.
    2. **Recursive Step:** Iterate from `i = start` to the end of the `characters` string.
    3. For each character, append it to `currentStringBuilder`.
    4. Make a recursive call `backtrack(i + 1, currentStringBuilder)` to find combinations starting with the current prefix.
    5. After the recursive call returns, remove the last character from `currentStringBuilder` to backtrack and explore other possibilities.
- `next()`:
    1. Retrieve the string at `combinations.get(currentIndex)`.
    2. Increment `currentIndex`.
    3. Return the retrieved string.
- `hasNext()`:
    1. Return `true` if `currentIndex` is less than the total size of the `combinations` list, `false` otherwise.

## Approach 2: On-the-fly Generation with Indices
This highly efficient approach avoids pre-computing all combinations. Instead, it calculates the next combination only when the `next()` method is called. It maintains the state of the current combination using an array of indices that point to characters in the input string, a technique often used for generating combinations iteratively.
**Time:** Constructor: `O(K)` to initialize the `indices` array.
`next()`: `O(K)`. In the worst case, we scan the entire `indices` array (`O(K)`) to find the pivot, and building the result string also takes `O(K)`.
`hasNext()`: `O(1)`. · **Space:** O(K), where K is the `combinationLength`, to store the `indices` array.
**Pros:** Extremely memory efficient, using only space proportional to the combination length.; Fast initialization (`O(K)`), as no heavy computation is done upfront.; Work is distributed across `next()` calls (lazy evaluation), which is ideal for typical iterator usage patterns.
**Cons:** The logic inside the `next()` method is more complex than in the pre-computation approach.; Each `next()` call has a slightly higher cost (`O(K)`) compared to the `O(1)` of the pre-computation approach.
### Explanation
The state of the iterator is represented by an array of integers, `indices`, of size `combinationLength`. Each integer in this array is an index into the original `characters` string. The constructor initializes this array to `[0, 1, ..., k-1]`, representing the first lexicographical combination.

The `next()` method performs two main tasks: it first constructs the string for the current `indices` and then updates the `indices` array to point to the next combination. To find the next combination, we scan the `indices` array from right to left, looking for the first index we can increment. Once we find such an index, we increment it and then reset all subsequent indices to be consecutive values following it. This guarantees that we move to the very next combination in lexicographical order. If we scan the whole array and find that all indices are at their maximum possible values, we know there are no more combinations left.

```java
class CombinationIterator {
    private String characters;
    private int n;
    private int k;
    private int[] indices;
    private boolean hasNext;

    public CombinationIterator(String characters, int combinationLength) {
        this.characters = characters;
        this.n = characters.length();
        this.k = combinationLength;
        this.indices = new int[k];
        // Initialize to the first combination: [0, 1, ..., k-1]
        for (int i = 0; i < k; i++) {
            this.indices[i] = i;
        }
        this.hasNext = true;
    }

    public String next() {
        // Build the current combination string
        StringBuilder sb = new StringBuilder();
        for (int index : indices) {
            sb.append(characters.charAt(index));
        }
        
        // Find the next combination's indices for the subsequent call
        // Start from the rightmost index and find the first one that can be incremented.
        int i = k - 1;
        while (i >= 0 && indices[i] == i + n - k) {
            i--;
        }

        if (i < 0) {
            // This was the last combination
            this.hasNext = false;
        } else {
            // Increment this index
            indices[i]++;
            // Reset all subsequent indices
            for (int j = i + 1; j < k; j++) {
                indices[j] = indices[j - 1] + 1;
            }
        }
        
        return sb.toString();
    }

    public boolean hasNext() {
        return this.hasNext;
    }
}
```
### Algorithm
- `CombinationIterator(characters, combinationLength)`:
    1. Store `characters`, its length `n`, and `combinationLength` `k`.
    2. Initialize an integer array `indices` of size `k`.
    3. Populate `indices` to represent the first combination: `indices[i] = i` for `i` from `0` to `k-1`.
    4. Set a boolean flag `hasNextFlag = true`.
- `next()`:
    1. Build the result string for the current combination by looking up `characters` using the values in the `indices` array.
    2. Prepare the `indices` for the *next* call. Find the rightmost index `i` that can be incremented. An index `indices[i]` can be incremented if it's not at its maximum possible value, which is `i + n - k`.
    3. Scan from `i = k-1` down to `0` to find the first index that is not at its maximum value.
    4. If no such index is found, it means the current combination is the last one. Set `hasNextFlag = false`.
    5. If an index `i` is found:
        a. Increment `indices[i]`.
        b. For all subsequent indices `j > i`, set `indices[j] = indices[j-1] + 1` to form the next lexicographically smallest combination.
    6. Return the string built in step 1.
- `hasNext()`:
    1. Return the `hasNextFlag`.

# Solutions
### Java

```java
class CombinationIterator { private int n ; private int combinationLength ; private String characters ; private StringBuilder t = new StringBuilder (); private List < String > cs = new ArrayList <>(); private int idx = 0 ; public CombinationIterator ( String characters , int combinationLength ) { n = characters . length (); this . combinationLength = combinationLength ; this . characters = characters ; dfs ( 0 ); } public String next () { return cs . get ( idx ++); } public boolean hasNext () { return idx < cs . size (); } private void dfs ( int i ) { if ( t . length () == combinationLength ) { cs . add ( t . toString ()); return ; } if ( i == n ) { return ; } t . append ( characters . charAt ( i )); dfs ( i + 1 ); t . deleteCharAt ( t . length () - 1 ); dfs ( i + 1 ); } } /** * Your CombinationIterator object will be instantiated and called as such: * CombinationIterator obj = new CombinationIterator(characters, combinationLength); * String param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */
```

### CPP

```cpp
class CombinationIterator { public: string characters ; vector < string > cs ; int idx ; int n ; int combinationLength ; string t ; CombinationIterator ( string characters , int combinationLength ) { idx = 0 ; n = characters . size (); this -> characters = characters ; this -> combinationLength = combinationLength ; dfs ( 0 ); } string next () { return cs [ idx ++ ]; } bool hasNext () { return idx < cs . size (); } void dfs ( int i ) { if ( t . size () == combinationLength ) { cs . push_back ( t ); return ; } if ( i == n ) return ; t . push_back ( characters [ i ]); dfs ( i + 1 ); t . pop_back (); dfs ( i + 1 ); } }; /** * Your CombinationIterator object will be instantiated and called as such: * CombinationIterator* obj = new CombinationIterator(characters, combinationLength); * string param_1 = obj->next(); * bool param_2 = obj->hasNext(); */
```

### Python

```python
class CombinationIterator : def __init__ ( self , characters : str , combinationLength : int ): def dfs ( i ): if len ( t ) == combinationLength : cs . append ( '' . join ( t )) return if i == n : return t . append ( characters [ i ]) dfs ( i + 1 ) t . pop () dfs ( i + 1 ) cs = [] n = len ( characters ) t = [] dfs ( 0 ) self . cs = cs self . idx = 0 def next ( self ) -> str : ans = self . cs [ self . idx ] self . idx += 1 return ans def hasNext ( self ) -> bool : return self . idx < len ( self . cs ) # Your CombinationIterator object will be instantiated and called as such: # obj = CombinationIterator(characters, combinationLength) # param_1 = obj.next() # param_2 = obj.hasNext()
```