Задача: 1286. Iterator for Combination
Сложность: medium

Создайте класс CombinationIterator:

CombinationIterator(string characters, int combinationLength) Инициализирует объект строкой characters, содержащей отсортированные различные строчные буквы английского алфавита, и числом combinationLength в качестве аргументов.
next() Возвращает следующую комбинацию длины combinationLength в лексикографическом порядке.
hasNext() Возвращает true, если и только если существует следующая комбинация.

Пример:

Input
["CombinationIterator", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[["abc", 2], [], [], [], [], [], []]
Output
[null, "ab", true, "ac", true, "bc", false]

Explanation
CombinationIterator itr = new CombinationIterator("abc", 2);
itr.next();    // return "ab"
itr.hasNext(); // return True
itr.next();    // return "ac"
itr.hasNext(); // return True
itr.next();    // return "bc"
itr.hasNext(); // return False

👨‍💻 Алгоритм:

1⃣Сгенерируйте все возможные бинарные битовые маски длины n: от 0 до 2^n - 1.

2⃣Используйте битовые маски с k установленными битами для генерации комбинаций из k элементов. Если n - 1 - j-й бит установлен в битовой маске, это указывает на присутствие символа characters[j] в комбинации и наоборот.

3⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

#include <vector>
#include <string>

class CombinationIterator {
private:
    std::vector<std::string> combinations;

public:
    CombinationIterator(std::string characters, int combinationLength) {
        int n = characters.size();
        int k = combinationLength;
        for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
            if (__builtin_popcount(bitmask) == k) {
                std::string curr;
                for (int j = 0; j < n; ++j) {
                    if (bitmask & (1 << (n - j - 1))) {
                        curr.push_back(characters[j]);
                    }
                }
                combinations.push_back(curr);
            }
        }
    }

    std::string next() {
        std::string res = combinations.back();
        combinations.pop_back();
        return res;
    }

    bool hasNext() {
        return !combinations.empty();
    }
};

Ставь 👍 и забирай 📚 Базу знаний