88. Combination Sum

Given distinct integer array candidates and target integer target, return all unique combinations where numbers sum to target. Same number may be used unlimited times.

Input: Distinct positive integer array candidates and positive integer target.

Output: All unique combinations summing to target, each sorted ascending.

Examples

Input: [2,3,6,7],7
Output: [[2,2,3],[7]]
Explanation: 2+2+3=7, 7=7.

Input: [2,3,5],8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: All combos summing to 8.

Input: [2],1
Output: []
Explanation: Cannot reach 1 using 2.

Constraints

• 1<=candidates.length<=30
• 2<=candidates[i]<=40
• All candidates distinct.
• 1<=target<=40

Asked by