Задача: 77. Combinations
Сложность: medium

Даны два целых числа n и k. Верните все возможные комбинации из k чисел, выбранных из диапазона [1, n].

Ответ можно вернуть в любом порядке.

Пример:

Input: n = 4, k = 2
Output: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
Explanation: There are 4 choose 2 = 6 total combinations.
Note that combinations are unordered, i.e., [1,2] and [2,1] are considered to be the same combination.

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

1⃣Инициализировать массив ответов ans и массив для построения комбинаций curr.

2⃣Создать функцию обратного вызова backtrack, которая принимает curr в качестве аргумента, а также целое число firstNum:
Если длина curr равна k, добавить копию curr в ans и вернуться.
Вычислить available, количество чисел, которые мы можем рассмотреть в текущем узле.
Итерировать num от firstNum до firstNum + available включительно.
Для каждого num, добавить его в curr, вызвать backtrack(curr, num + 1), а затем удалить num из curr.

3⃣Вызвать backtrack с изначально пустым curr и firstNum = 1.
Вернуть ans.

😎 Решение:

function combine($n, $k) {
    $ans = [];

    $backtrack = function (&$curr, $firstNum) use ($n, $k, &$ans, &$backtrack) {
        if (count($curr) === $k) {
            array_push($ans, $curr);
            return;
        }

        $need = $k - count($curr);
        $remain = $n - $firstNum + 1;
        $available = $remain - $need;

        for ($num = $firstNum; $num <= $firstNum + $available; $num++) {
            array_push($curr, $num);
            $backtrack($curr, $num + 1);
            array_pop($curr);
        }
    };

    $backtrack([], 1);
    return $ans;
}

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