Why it works
- The call below gets i, not i + 1, so the same candidate may be taken again, as in [4, 4]; it never gets an index before i, so every combination is built in one order only, smallest first, and [5, 3] never repeats [3, 5].
- All candidates are positive, so left only shrinks: at left = 0 the path is an answer, and a path whose next candidate is bigger than left can never reach it.
- After sorting, the first candidate bigger than left means every later one is bigger too, so break cuts the whole rest of the loop instead of checking each.
Complexity
Time O(n^(t / m) × t / m) in the worst case, where t is the target and m the smallest candidate: a path holds at most t / m numbers, each picked from at most n, and each answer is copied. Memory O(t / m) besides the answer: the path and the call stack.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗