82. Combination Sum

Medium · Backtracking

Find all unique combinations of numbers that sum to a target value. You are given an array of distinct positive integers (candidates) and a target sum. Each candidate number can be used unlimited times. Return every combination that adds up to the target, where each combination is sorted in ascending order and the list of combinations is sorted lexicographically. For example, with candidates [2,3,6,7] and target 7, the valid combinations are [2,2,3] and [7].

Examples

Example 1
Input: [[2,3,6,7], 7]
Output: [[2,2,3],[7]]
Explanation: Two combinations sum to 7
Example 2
Input: [[2,3,5], 8]
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: Three combinations sum to 8

Constraints