753. Combination Sum I (Unlimited Use)

Given an array of DISTINCT positive integers candidates (duplicates in input should be collapsed to unique values) and a positive integer target, return all unique combinations of candidates whose elements sum to exactly target. Each candidate value may be used an UNLIMITED number of times. The output must be deterministic:
1. Each combination is listed with its elements in non-decreasing order.
2. The list of combinations is sorted lexicographically.
If no combination exists, return an empty list.

Input: An array of positive integers and a target, formatted as "[c1,c2,...], target".

Output: Return a list of lists in canonical sorted order.

Examples

Input: [2,3,6,7], 7
Output: [[2,2,3],[7]]
Explanation: 2+2+3 = 7 and 7 alone are the two ways.

Input: [2,3,5], 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: Three combinations in sorted order.

Input: [2], 1
Output: []
Explanation: No combination reaches 1.

Constraints

• 1 <= candidates.length <= 15
• 1 <= candidates[i] <= 20
• 1 <= target <= 30

Asked by