Задача: 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⃣Теперь у вас есть все заранее вычисленные комбинации. Извлекайте их одну за другой по каждому запросу.

😎 Решение:

class CombinationIterator {
    constructor(characters, combinationLength) {
        this.combinations = [];
        let n = characters.length;
        let k = combinationLength;
        for (let bitmask = 0; bitmask < (1 << n); bitmask++) {
            if (bitmask.toString(2).split('1').length - 1 === k) {
                let curr = [];
                for (let j = 0; j < n; j++) {
                    if (bitmask & (1 << (n - j - 1))) {
                        curr.push(characters[j]);
                    }
                }
                this.combinations.push(curr.join(''));
            }
        }
    }

    next() {
        return this.combinations.pop();
    }

    hasNext() {
        return this.combinations.length > 0;
    }
}

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