[Python3] | O(k) | On the fly | Using stacks
The approach uses backtracking with the help of stacks. There are two cases:\n1. We backtrack when we have reached the end of available characters\n2. We backtr
The approach uses backtracking with the help of stacks. There are two cases:\n1. We backtrack when we have reached the end of available characters\n2. We backtrack when, from the current character, we cannot reach a valid end character.\n\nWe use a stack to store the indices of the characters and backtrack as mentioned above. See code below:\n\n```\nclass CombinationIterator:\n\n    def __init__(self, characters: str, combinationLength: int):\n        self.chars = sorted(list(set(characters)))\n        self.nchars = len(self.chars)\n        self.l = combinationLength\n        self.stack = [i for i in range(self.l)]\n    \n    def next(self) -> str:\n        if not self.stack:\n            return \'\'\n        \n        ret = \'\'.join(self.chars[i] for i in self.stack)\n\n        if self.stack[-1] < self.nchars - 1:\n            self.stack[-1] += 1\n        else:\n\t\t    # Backtrack because we have reached the end\n            while self.stack and self.stack[-1] >= self.nchars - 1:\n                self.stack.pop()\n                if self.stack:\n                    self.stack[-1] += 1\n            \n\t\t\t# Backtrack because we cannot form a valid combination from the current position.\n            while self.stack and (self.stack[-1] + (self.l - len(self.stack))) >= self.nchars:\n                self.stack.pop()\n                if self.stack:\n                    self.stack[-1] += 1\n            \n\t\t\t# If there are valid combination to be formed, include the indices of the character\n            if self.stack:\n                while len(self.stack) < self.l:\n                    self.stack.append(self.stack[-1] + 1)\n                    \n        return ret\n                            \n    def hasNext(self) -> bool:\n        if self.stack:\n            return True\n        return False\n```
[]