Почему это работает
- Каждый вызов берёт только числа после последнего в пути, поэтому каждое сочетание собирается один раз, по возрастанию, и [2, 1] не повторяет [1, 2].
- Путь сохраняется ровно тогда, когда в нём k чисел; потом последнее число убирается, и цикл ставит на его место следующее.
- Если осталось need мест, то начало больше n − need + 1 оставляет меньше need чисел, и ветка не может закончиться: граница цикла пропускает её, не спускаясь.
Сложность
Время O(k × C(n, k)): граница цикла даёт каждому начатому пути дойти до k чисел, поэтому вызовов не больше k на ответ, и каждый ответ — копия k чисел. Память O(k) помимо ответа: путь и стек вызовов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗