[C++] 12ms (Fastest to Date) Bit-based Solution with Combinatorics Explained, 100% Time, ~90% Space
Basic idea: computing all the possible combinations by brute force is ridicolously expensive.\n\nInstead, I can make it work just as fine, if not better, if I h
Basic idea: computing all the possible combinations by brute force is ridicolously expensive.\n\nInstead, I can make it work just as fine, if not better, if I have an array of booleans in order to map what is going to be the next combination, initialising it with the first `combinationLength` values as `true` and the rest to `false`, then at each iteration, after I generate my string, I will update it shifting the first available `true` that can be shifted to the right by one position and aligning all the other `true`s at its right to be just after it (and will do so with a neat call to sort!).\n\nThis is the core of my solution, all wrapped in `advanceCombs` that starts checking from the leftmost all the available bits (and always just the first `s.size` ones) and builds its way until it finds a match.\n\nTo give this bit of logic an example, immagine you have the string `"abcde"` and need to generate combinations of `3` unique characters: your array will be like this (remember in every case we only need to consider the first `s.size()` characters, so the values after the fifth in parentheses are still there, but they jusst won\'t be used for this specific case - a string of length `5`):\n\n```cpp\n1 1 1 0 0 (0 0 0 0 0 0 0 0 0 0) => abc\n1 1 0 1 0 (0 0 0 0 0 0 0 0 0 0) => abd\n1 1 0 0 1 (0 0 0 0 0 0 0 0 0 0) => abe\n1 0 1 1 0 (0 0 0 0 0 0 0 0 0 0) => acd\n1 0 1 0 1 (0 0 0 0 0 0 0 0 0 0) => ace\n1 0 0 1 1 (0 0 0 0 0 0 0 0 0 0) => ade\n0 1 1 1 0 (0 0 0 0 0 0 0 0 0 0) => bcd\n0 1 1 0 1 (0 0 0 0 0 0 0 0 0 0) => bce\n0 1 0 1 1 (0 0 0 0 0 0 0 0 0 0) => bde\n0 0 1 1 1 (0 0 0 0 0 0 0 0 0 0) => cde\n```\n\nIf not such a value is any longer possible, as it is the case we just update `hasMoreCombs` to be `false`.\n\nMy code:\n\n```cpp\nclass CombinationIterator {\npublic:\n    string s;\n    bool combs[15];\n    int k;\n    bool hasMoreCombs = true;\n    void advanceCombs() {\n        //move the first availabile and rightmost 1 left one step, sort from there\n        for (int i = s.size() - 1; i; i--) {\n            if (!combs[i] && combs[i - 1]) {\n                swap(combs[i], combs[i - 1]);\n                sort(begin(combs) + i + 1, begin(combs) + s.size(), greater<>());\n                return;\n            }\n        }\n        hasMoreCombs = false;\n    }\n    \n    CombinationIterator(string &characters, int combinationLength) {\n        s = characters;\n        k = combinationLength;\n        // initialising combs for our very first string\n        for (int i = 0; i < 15; i++) combs[i] = i <  k;\n    }\n    \n    string next() {\n        // generating the current next string\n        string res;\n        for (int i = 0; i < s.size(); i++) if (combs[i]) res.push_back(s[i]);\n        // preparing the next combinations\n        advanceCombs();\n        return res;\n    }\n    \n    bool hasNext() {\n        // most complex bit of logic ever here :D\n        return hasMoreCombs;\n    }\n};\n```\n\nVersion of `advanceCombs` without sorting - as you might have guessed the performance improvement is not massive, but something is still there:\n\n```cpp\n    void advanceCombs() {\n        // keeping track of how many true/1s we have seen so far\n        int onesSeen = 0;\n        //move the first availabile and rightmost 1 left one step, sort from there\n        for (int i = s.size() - 1; i; i--) {\n            onesSeen += combs[i];\n            if (!combs[i] && combs[i - 1]) {\n                swap(combs[i], combs[i - 1]);\n\t\t\t\t// moving all the previous 1s to the right of the swapped one\n                for (int j = i + 1; j < s.size(); j++) combs[j] = onesSeen-- > 0;\n                return;\n            }\n        }\n        hasMoreCombs = false;\n    }\n```\n\nEdit: okay, bragging time - it looks like actually my latest change made me code the fastest ever submitted:\n\n![image](https://assets.leetcode.com/users/images/d0e08503-7596-4bc5-8b09-0553aff3f4ee_1597401020.7996266.png)\n\nAlso courtesy of this extra bit taken from [MrGhasita\'s solution](https://leetcode.com/problems/iterator-for-combination/discuss/789110/) (thanks mate, you are legend!):\n\n```cpp\nstatic auto speedup = []() {\n    ios::sync_with_stdio(false);\n    cin.tie(nullptr);\n    cout.tie(nullptr);\n    return nullptr;\n}();\n```
['String', 'C', 'Combinatorics', 'C++']