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