Почему это работает
- После сортировки равные числа стоят рядом, поэтому повтор легко заметить: он равен числу прямо перед ним.
- В одном вызове ветка, которая начинается с повтора, собрала бы те же подмножества, что ветка первой копии, поэтому i > start при nums[i] == nums[i - 1] пропускаем.
- При i == start число встаёт за только что взятым, а не начинает соседнюю ветку, поэтому вторая 3 после первой даёт новое: так [3, 3] и [1, 3, 3] появляются ровно один раз.
Сложность
Время O(n × 2ⁿ): сортировка — O(n log n), потом не больше 2ⁿ вызовов, и каждый копирует путь длиной до n. Память O(n) помимо ответа: путь и стек вызовов не глубже n.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗