Gosper’s Hack, also beating 90+%
One can apply an algorithm named "Gosper\u2019s Hack" to solve this problem easily, but the 1 bits in the binary sequence generated by Gosper\'s Hack must be in
One can apply an algorithm named "Gosper\u2019s Hack" to solve this problem easily, but the `1` bits in the binary sequence generated by Gosper\'s Hack must be interpreted as letters *not used* in the resulting string. So, the `1`s in the complement of each term in this binary sequence repreents letters used in the resulting string.\n\nSee https://programmingforinsomniacs.blogspot.com/2018/03/gospers-hack-explained.html for a decent explanation of what "Gosper\u2019s Hack" is.\n\nSee below for my solution:\n\n```\nclass CombinationIterator {\npublic:\n    CombinationIterator(string const& characters, int const combinationLength) :\n\t    nchar_(characters.size()),\n\t\tcombLen_(combinationLength),\n        limit_(1 << nchar_),\n\t\tcomb_((1 << (nchar_ - combLen_)) - 1) {\n        m_.reserve(nchar_);\n        for (int i = 0; i < nchar_; ++i)\n            m_[1 << (nchar_ - 1 - i)] = characters[i];\n    }\n    \n    string next() {\n        string s(combLen_, \'\\0\');\n        {\n            auto x = ~comb_;\n            for (int i = combLen_ - 1; i >= 0; --i) {\n                auto const b = x & -x;\n                s[i] = m_[b];\n                x &= ~b;\n            }\n        }\n        \n        // BEGIN: Gosper\u2019s Hack\n        auto const c = comb_ & - comb_;\n        auto const r = comb_ + c;\n        comb_ = (((r ^ comb_) >> 2) / c) | r;\n        // END: Gosper\u2019s Hack\n\t\t\n        return s;\n    }\n    \n    bool hasNext() const {\n        return comb_ < limit_;\n    }\nprivate:\n    int const nchar_;\n    int const combLen_;\n    unsigned int const limit_;\n    unsigned int comb_;\n    unordered_map<unsigned int, char> m_;\n};\n```
[]