Задача: 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 {
    private $combinations;

    function __construct($characters, $combinationLength) {
        $this->combinations = [];
        $n = strlen($characters);
        $k = $combinationLength;
        for ($bitmask = 0; $bitmask < (1 << $n); $bitmask++) {
            if (substr_count(decbin($bitmask), '1') == $k) {
                $curr = [];
                for ($j = 0; $j < $n; $j++) {
                    if ($bitmask & (1 << ($n - $j - 1))) {
                        $curr[] = $characters[$j];
                    }
                }
                $this->combinations[] = implode('', $curr);
            }
        }
    }

    function next() {
        return array_pop($this->combinations);
    }

    function hasNext() {
        return count($this->combinations) > 0;
    }
}

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