C++ / Python Three Simple and Clean Solutions, Bitmasking / Pre-Calculating
Solution I - Bitmasking\nWe use a bitmask to inticate which letters to use at each combination.\nThe mask is the length of the chars (which is max 15 - int) and
**Solution I - Bitmasking**\nWe use a bitmask to inticate which letters to use at each combination.\nThe mask is the length of the chars (which is max 15 - int) and the idea is that we should always have `combinationLength` set bits.\nSo we start with the leftmost bit set, because we want to start with the largest value.\nThen, at each iteration, we decrement `bitmask` until we have exactly `combinationLength` set bits, and then we just loop through the `chars` and add the ones with the corresponding bit set.\n```\nclass CombinationIterator {\npublic:\n    CombinationIterator(string characters, int combinationLength) : \n                n(characters.size()), comb_len(combinationLength), chars(characters) {\n        bitmask = (1 << n) - 1;\n    }\n    \n    string next() {\n        while (bitmask >= 0 && countSet(bitmask) != comb_len) bitmask--;\n        \n        string res = "";\n        for (int i = 0; i < n; i++) {\n            if (bitmask & (1 << (n - i - 1))) res += chars[i];\n        }\n        \n        bitmask--;\n        return res;\n    }\n    \n    bool hasNext() {\n        while (bitmask >= 0 && countSet(bitmask) != comb_len) bitmask--;\n        return bitmask >= 0;\n    }\n    \n    int countSet(int mask) {\n        int count = 0;\n        while (mask) {\n            count += mask & 1;\n            mask >>= 1;\n        }\n        return count;\n    }\n    \nprivate:\n    int bitmask, n, comb_len;\n    string chars;\n};\n```\n****\n**Solution II - Backtracking**\nWe generate all combinations in advance, using classic backtracking.\nIn each iteration, we add the next number ito `curr`, send it as is to `backtrack`, and then remove it and try to add the next number.\nWhen the combination reaches the size `n` = `combinationLength`, we add it to `combs`.\nWe keep an iterator `i` to know where\'s the next combination and when we\'re at the end and we don\'t have a next.\n```\nclass CombinationIterator {\npublic:\n    void backtrack(string curr, string chars, int n, int start) {\n        if (curr.size() == n) {\n            combs.push_back(curr);\n            return;\n        }\n        \n        for (int i = start; i < chars.size(); i++) {\n            curr.push_back(chars[i]);\n            backtrack(curr, chars, n, i+1);\n            curr.pop_back();\n        }\n    }\n    \n    CombinationIterator(string characters, int combinationLength) {\n        backtrack("", characters, combinationLength, 0);\n    }\n    \n    string next() {\n        return combs[i++];\n    }\n    \n    bool hasNext() {\n        return i < combs.size();\n    }\n    \nprivate:\n    vector<string> combs;\n    int i = 0;\n};\n```\n****\n**Solution III - Using Built-in**\nIn this solution, we are simply using a built-in function called `combinations`.\nWe use it to generate all combinations.\n```\nclass CombinationIterator:\n    def __init__(self, characters: str, combinationLength: int):\n        self.allCombinations = list(combinations(characters, combinationLength))\n        self.count = 0\n\n    def next(self) -> str:\n        self.count += 1\n        return "".join(self.allCombinations[self.count-1])\n        \n    def hasNext(self) -> bool:\n        return self.count < len(self.allCombinations)\n```\n**Like it? please upvote!**
['C']