Почему это работает
- Вызов ниже получает i, а не i + 1, поэтому тот же кандидат можно взять ещё раз, как в [4, 4]; индекса меньше i он не получает, поэтому каждый набор собирается в одном порядке, от меньшего к большему, и [5, 3] не повторяет [3, 5].
- Все кандидаты положительные, поэтому left только уменьшается: при left = 0 путь — это ответ, а путь, у которого следующий кандидат больше left, до цели уже не дойдёт.
- После сортировки первый кандидат больше left означает, что и все следующие больше, поэтому break отрезает весь остаток цикла, а не проверяет каждого.
Сложность
Время O(n^(t / m) × t / m) в худшем случае, где t — цель, а m — наименьший кандидат: в пути не больше t / m чисел, каждое выбирается из не более чем n, и каждый ответ копируется. Память O(t / m) помимо ответа: путь и стек вызовов.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗