Iterator For Combination - Leetcode Solution

Problem Description:

Design an Iterator class that iterates over a combination of n elements taken k at a time.

The class should have the following methods:

• Constructor which accepts two integers n and k and initializes an internal list of combinations.
• hasNext() which returns True if there exists a combination of elements to be iterated over.
• next() which returns the next combination of elements in the list.

Constraints:

• 1 ≤ n ≤ 20
• 1 ≤ k ≤ n

Solution:

To solve the Iterator For Combination problem, we can use backtracking to generate all possible combinations of length k from the input array of length n.

We can define an iterator class with an internal list of all possible combinations, which we can pre-compute in the constructor using backtracking. We can then implement the next() method to return the next combination in the list and the hasNext() method to check if there are any more combinations left to be iterated over.

Here is the Python implementation of the Iterator class:

class CombinationIterator:

    def __init__(self, n: int, k: int):
        self.combinations = []
        self.generate_combinations(n, k, [], 1)
        self.ptr = 0
        
    def generate_combinations(self, n, k, curr_combo, start):
        if len(curr_combo) == k:
            self.combinations.append("".join(curr_combo))
            return
        for i in range(start, n+1):
            curr_combo.append(str(i))
            self.generate_combinations(n, k, curr_combo, i+1)
            curr_combo.pop()
            
    def next(self) -> str:
        res = self.combinations[self.ptr]
        self.ptr += 1
        return res
            
    def hasNext(self) -> bool:
        return self.ptr < len(self.combinations)

The generate_combinations() method implements backtracking to generate all possible combinations of length k from the input array of length n. We use a helper method to convert the integer array to a string, as required by the problem statement.

The iterator's constructor initializes the internal list of combinations by calling the generate_combinations() method and sets the pointer to the first element.

The next() method returns the next combination in the list and updates the pointer, while the hasNext() method checks if there are more combinations left to be iterated over.

Time Complexity:

The time complexity of generating all combinations is O(n choose k), where n choose k is the binomial coefficient. The time complexity of initializing the iterator is O(n choose k), and the time complexity of each next() and hasNext() operation is O(1).

Space Complexity:

The space complexity of the iterator is O(n choose k) to store the list of combinations. Additionally, the generate_combinations() method has a space complexity of O(k) for the stack space used in the recursive calls.

1