✅ All 5 Solutions w/ Detailed Explanations | Bitmask + Backtrack + On-The-Fly + Gosper's Hack
We are given a string s of length L and we are required to return combinations of s of length n in lexicographical order.\n\n---\n\n\u2714\uFE0F Solution - I (P
We are given a string *`s`* of length *`L`* and we are required to return combinations of *`s`* of length *`n`* in lexicographical order.\n\n---\n\n***\u2714\uFE0F Solution - I (Precompute all Combinations w/ Bitmasking)***\n\nThe problem is basically consists of generating combinations of length *`n`* from a string of length *`L`*. The simplest way we can solve it is by computing all combinations of given string and store them in lexicographically sorted order and then return one after another. \n\n* The combinations can be be generated through a standard bitmasking approach. \n* A mask of *`L`* bits can generate all **<code>2<sup>L</sup></code>** combination strings of *`s`*. \n* Each bit of mask is used to denote whether the corresponding character of *`s`* will be chosen or not. \n\nFor eg. Consider the following illustration -\n\n```\ns = "abc"  ,  L = size(s) = 3\nIterate over mask from 0 to 2^L. \nA set bit in mask denotes corresponding character must be chosen & vice-versa\n\n\tMask             Combination\n  ("abc")\n    000      ->         ""\n    001      ->         "c"\n    010      ->         "b"\n    011      ->         "bc"\n    100      ->         "a"\n    101      ->         "ac"\n    110      ->         "ab"\n    111      ->         "abc"\n```\n\nThese are all the combinations possible for *`s`*. We only need to consider strings with length *`n`*. These only occur  in **mask having `n` set bits**.\n\nThus, we can summarize algorithm to generate combinations of string as -\n1. Iterate through *`mask`* from **<code>1 to 2<sup>L</sup></code>**.\n2. Consider only *`mask`* having number of set bits equal to *`L`*.\n3. Iterate through all *`L`* bits of *`mask`* and add the character corresponding to `j`th set bit(*`s[j]`*) into *`combination`* string.\n\nFinally, we maintain a lexicographical order of all combination string by keeping all strings in a sorted set *`comb`* and then returning them one by one.\n\n**C++**\n\n```cpp\nclass CombinationIterator {\n    string s;\n    int n, L;\n    set<string> comb;\n    set<string>::iterator cur;\n\t\n    void generate(string& s, int n) {\n        for(int mask = 0; mask < 1 << L; mask++) {         // iterate mask from [0, 2^L)\n            if(__builtin_popcount(mask) != n) continue;    // only mask with number of set bits = n must be considered\n            string combination = "";\n            for(int j = 0; j < L; j++)                     // traverse over bits of current mask\n                if(mask & 1 << j)                          // if jth bit is set, then\n                    combination += s[j];                   // push jth character of s\n            comb.insert(move(combination));                // insert the constructed string into set\n        }\n        cur = begin(comb);\n    }\npublic:\n    CombinationIterator(string& s, int n) : s(s), n(n), L(size(s)) { generate(s, n); }\n\t\n    string next()  { return *cur++; }                      // return increment to iterator next string\n    bool hasNext() { return cur != end(comb); }         // check if all strings are iterated\n};\n```\n\n\n***Time Complexity :*** \n1. **`CombinationIterator` :** **<code>O(2<sup>L</sup>)</code>**, where *`L`* is the length of given input string `s`. We require <code>O(2<sup>L</sup>)</code> to iterate over the range <code>[0, 2<sup>L</sup>)</code>. The number of strings generated is equal to **<code><sup>L</sup>C<sub>n</sub></code>**, where *<code><sup>L</sup>C<sub>n</sub></code>* is the number of ways of choosing `n` objects from a total of `L` objects. Each time, we iterate over `L` bits and construct strings of length `n` which are then inserted into sorted set. This all requires <code>O(L + nlog(<sup>L</sup>C<sub>n</sub>))</code> and this happens <code><sup>L</sup>C<sub>n</sub></code> times. Thus, the overall time complexity is *<code>O(2<sup>L</sup> + <code><sup>L</sup>C<sub>n</sub></code>(L + nlog(<code><sup>L</sup>C<sub>n</sub></code>)))</code>*\n\n\tHowever, the only dominant term here is <code>O(2<sup>L</sup>)</code>, since <code><sup>L</sup>C<sub>n</sub></code> only denotes choosing subset of combinations while <code>2<sup>L</sup></code> is the total possible combinations.\n\n2. **`next` :** **`O(1)`**, since we are only moving iterator of a set which takes `O(1)`\n3. **`hasNext` :** **`O(1)`**, since we only check if iterator has reached end which again takes `O(1)`.\n\n\n***Space Complexity :*** **<code>O(<sup>L</sup>C<sub>n</sub>)</code>**, the number of string combinations of length `n` possible from a string of length `L` is equal to <code><sup>L</sup>C<sub>n</sub></code> and each string has a length `n`.\n\n---\n\n\u2714\uFE0F ***Solution - II (Backtracking)***\n\nWe can also use a standard backtracking approach to generate all combinations. For each of characters in `s`, we can choose it, generate a combination string by recursive call to `backtrack` and backtrack by popping that character and try forming another combination by choosing the next one. \n\nIn this case, since the string `s` is sorted and we are choosing characters 1-by-1 starting from 1st character in `s`, the backtrack will generate all strings in sorted order. So, we can simply store all the strings in an array and return one by one as per the calls we get.\n\n```cpp\nclass CombinationIterator {\n    string s;\n    int n;\n    vector<string> comb;\n    vector<string>::iterator cur;\n\n    void backtrack(string& s, int n, string& combination, int i) {\n        if(size(combination) == n) {                 // prune further search when size == n\n            comb.push_back(combination);             // insert constructed combination into array\n            return;\n        }\n        for(int j = i; j < size(s); j++) {\n            combination += s[j];                     // append s[j] to combination and\n            backtrack(s, n, combination, j+1);       // try forming combinations with it\n            combination.pop_back();                  // backtrack to try other characters at this position\n        }\n    }\npublic:\n    CombinationIterator(string& s, int n) : s(s), n(n) {\n        string combination{""};\n        backtrack(s, n, combination, 0);\n        cur = begin(comb);\n    }\n    string next()  { return *cur++; }\n    bool hasNext() { return cur != end(comb); }\n};\n```\n\n***Time Complexity :*** \n1. **`CombinationIterator` :** **<code>O(<sup>L</sup>C<sub>n</sub>)</code>** Here, each string combination of length `n` is generated once and there are total of <code><sup>L</sup>C<sub>n</sub></code> combination possible.\n2. **`next` :** **`O(1)`**\n3. **`hasNext` :** **`O(1)`**\n\n\n***Space Complexity :*** **<code>O(<sup>L</sup>C<sub>n</sub>)</code>**, same as above\n\n\n---\n\n***\u2714\uFE0F Solution - III (On-the-Fly Dynamic Generation)***\n\nIn the 1st case, we generated all the possible combinations and stored it in a set to sort lexicographically and then returned one by one. We can optimize the space by generating on the fly. The strings generated in the above case were not lexicographically sorted, but if we observe properly, they were infact generated in exact reverse of lexicographically  sorted order. \n\nWe can use this fact and generate it in lexicographical order by iterating over the mask from 2<sup>L</sup> down to 0. Let\'s see example of how this would generate strings\n\n```\ns = "abc"\nL = size(s) = 3\nIterate over mask from 0 to 2^L\n\n\tMask             Combination\n  ("abc")\n    111      ->         "abc"\n    110      ->         "ab"\n    101      ->         "ac"\n    100      ->         "a"\n    011      ->         "bc"\n    010      ->         "b"\n    001      ->         "c"\n    000      ->         ""\n\nNow, we see that strings of all length are generated lexicographically\n```\n\nWe also need to make another change in `Solution-I` of reading the mask from Most Significant Bit (MSB) down to LSB to generate it lexicographically.\n\n```cpp\nclass CombinationIterator {\n    string s;\n    int n, L, mask;\npublic:\n    CombinationIterator(string s, int n) : s(s), L(size(s)), n(n), mask((1<<L) - 1) { }\n    string next() {\n        if(!hasNext()) return "";                 // updates mask to next lower integer having n set bits\n        string combination = "";\n        for(int j = L-1; j >= 0; j--)             // iterate over mask from MSB to LSB\n                if(mask & 1 << j)                 // if a bit is set,\n                    combination += s[L-1-j];      // then add character corresponding to that bit\n        mask--;                                   // move to next mask\n        return combination;\n    }\n    bool hasNext() {\n\t\t// checks if another mask with n set bits exists before we reach mask=0\n        while(mask >= 0 && __builtin_popcount(mask) != n) mask--; \n        return mask >= 0;\n    }\n};\n```\n\n***Time Complexity :*** \n1. **`CombinationIterator` :** **<code>O(<sup>L</sup>C<sub>n</sub>)</code>** Here, each string combination of length `n` is generated once and there are total of <code><sup>L</sup>C<sub>n</sub></code> combination possible.\n2. **`next` :** **<code>O(2<sup>L-1</sup>)</code>**, due to `hasNext` call.\n3. **`hasNext` :** **<code>O(2<sup>L-calls</sup> - 2<sup>L-calls-1</sup>)</code>**, where *`calls`* is the number of calls made to `next`. The number of iteration performed is equivalent to the distance between two integers having `n` number of set bits. In the worst case, `n=1` and we need to iterate mask between two adjacent powers of 2. With each call, the mask is decremented and we move to the lower power of 2. \n\tLet me know if there\'s a mistake or a better way to express this time complexity\n\n\n***Space Complexity :*** **`O(L)`** we are only storing a copy of input string `s`. All the combination strings are generated on the fly and dont require any space\n\n---\n\n***\u2714\uFE0F Solution - IV (Optmized Bit-manipulation)***\n\nIn the above solution, the huge time complexity is mainly caused by the calls to `hasNext` which basically just iterates and updates *`mask`* to the next smaller integer having `n` set bits. \n\nBut can we do better? Do we really need to iterate through all integers checking number of set bits? Or is there a better way to get next smaller integer with *`n`* set bits?\n\nConsider the following example -\n\n```\ns = "abcd",  n = 2\nWe have L = s.length = 4\n\nWe iterate through mask in the following order (I have omiited intermediate numbers that we iterate through) -\n\nstep\t      Mask            Combination\n\t     ("a b c d e")\n1.         1 1 1 0 0    ->       "abc"\n2.         1 1 0 1 0    ->       "abd"\n3.         1 1 0 0 1    ->       "abe"\n4.         1 0 1 1 0    ->       "acd"\n5.         1 0 1 0 1    ->       "ace"\n6.         1 0 0 1 1    ->       "ade"\n7.         0 1 1 1 0    ->       "bcd"\n8.         0 1 1 0 1    ->       "bce"\n9.         0 1 0 1 1    ->       "bde"\n10.        0 0 1 1 1    ->       "cde"   => Explored all combination - Stop.\n```\n\n**See a pattern in above example? (Hint: Watch how the 1s move).** For each mask -\n* If rightmost set bit is not at the end (LSB), we are simply **right-shifting the rightmost set bit**\n* If rightmost set bit at the end - \n\t* We consider all 1s at the right-end as a single group. Then we find a rightmost set bit that is not part of this group and shift it 1 position to the right (see how mask is updated at step-3, 5, 6). Then all the right-end group of 1s are moved and pasted just to the right of above position.\n\t* What if we cant find a set bit that is not part of rightmost group of 1? This simply means we have explored all possible combinations (see step 10)\n\nThus, we can use **bit-manipulation on the mask to find the next smaller integer with *`n`* set bits in O(1)**. The following code is a bit implementation heavy but if you understood the above steps, it wont be hard to understand the code as well. You can find another similar implementation in **[@astroash\'s Permuting Pointers](https://leetcode.com/problems/iterator-for-combination/discuss/1576763/C%2B%2B-or-Permuting-Pointers!-or-Pictures-%2B-Detailed-Explanation-%2B-Commented-Code-or-NovemberChallenge)** post as well which might be a bit easier to understand if you aren\'t well-versed with bit-manipulation.\n\n```cpp\nclass CombinationIterator {\n    string s;\n    int n, L, mask = 0;\n    bool has_next = true;\npublic:                            //  initially set bits corresponding \u2193 to 1st n bits of s\n    CombinationIterator(string s, int n) : s(s), L(size(s)), n(n), mask((1<<n)-1 << L-n) { }\n    string next() {\n        string combination = "";\n        for(int j = L-1; j >= 0; j--)             // iterate over mask from MSB to LSB\n                if(mask & 1 << j)                 // if a bit is set,\n                    combination += s[L-1-j];      // then add character corresponding to that bit\n        updateMask();                             // move to next mask\n        return combination;\n    }\n    void updateMask() {\n        int rightMostBit = mask & -mask;            // get right-most set bit\n        if(rightMostBit != 1) {                     // if last bit(LSB) is not set, just right-shift\n            mask ^= rightMostBit;                   // unset right-most bit\n            mask |= rightMostBit>>1;                // and set its right-adjacent bit\n        } \n        else {\n            // all 1s occur adjacently at right-end means we explored all\n            if((mask & (mask + 1)) == 0) { has_next = false; return; } \n            \n            int rightOnesCnt = 0, pos = 0;           // get group of continous 1s at right\n            while(mask & 1 << pos) {\n                mask ^= 1 << pos;                    // unset these group of 1s\n                rightOnesCnt++, pos++;\n            }\n            int rightMostBit = mask & -mask;         // now get rightmost set bit position & right-shift it\n            mask ^= rightMostBit;                    // First: unset it\n            mask |= rightMostBit >>= 1;              // Then : set its right-adjacent\n            while(rightOnesCnt--)                    // paste rightmost group of 1s that we had unset above /\n                mask |= rightMostBit >>= 1;          // right-adjacent to rightMostBit that was right-shifted above\n        }\n    }\n    bool hasNext() { return has_next; }\n};\n```\n\n***Time Complexity :*** \n1. **`CombinationIterator` :** **<code>O(L)</code>** We just save a copy of input string `s` which takes `O(L)` and manually set the initial mask which takes `O(n)`. Thus, the total time complexity becomes `O(L+n) \u2248 O(L)`\n2. **`next` :** **<code>O(L)</code>**, We just take the `mask` and generate a string corresponding to set bits in the it. This requires `O(L)` time. The `updateMask()` function is a pure bit-manipulation function which only requires `O(1)` time.\n3. **`hasNext` :** **<code>O(1)</code>** We are simply returning a boolean variable that we store.\n\n***Space Complexity :*** **`O(L)`**, required for storing input string `s`\n\n---\n\n***\u2714\uFE0F Solution - V (Optimized Bit-manipulation - Gosper\'s Hack)***\n\nWell if the above bit-manipulation felt complex, then be glad to know that there does exist a much simpler way to obtain the next smaller integer having `n` set bits using a modification of **[Gosper\'s hack](https://stackoverflow.com/a/18930479/13602076)**. You can read about it in "Bitwise tricks and techniques" in *The Art of Computer Programming* Book. \n\nThe below `updateMask` function does the same thing that happens above, just concisely (much concisely :) )\n\n```cpp\nclass CombinationIterator {\n    string s;\n    int n, L, mask = 0;\n    bool has_next = true;\npublic:\n    CombinationIterator(string s, int n) : s(s), L(size(s)), n(n), mask((1<<n)-1 << L-n) { }\n    string next() {\n        string combination = "";\n        for(int j = L-1; j >= 0; j--)             // iterate over mask from MSB to LSB\n                if(mask & 1 << j)                 // if a bit is set,\n                    combination += s[L-1-j];      // then add character corresponding to that bit\n        updateMask();                             // move to next mask\n        return combination;\n    }\n    // using Gospel\'s hack\n    void updateMask() {\n        int t = mask + 1, u = t ^ mask, v = t & mask;\n        mask = v - (v & -v) / (u + 1);\n        has_next = mask;\n    }\n    bool hasNext() { return has_next; }\n};\n```\n\nAll complexities remain the same as above.\n\n***Time Complexity :*** \n1. **`CombinationIterator` :** **<code>O(L)</code>**\n2. **`next` :** **<code>O(L)</code>**\n3. **`hasNext` :** **<code>O(1)</code>**\n\n***Space Complexity :*** **`O(L)`**\n\n---\n---\n\n\uD83D\uDCBBIf there are any suggestions / questions / mistakes in my post, comment below \uD83D\uDC47 \n\n---\n---
[]