Medium

Quiz

#39 Combination Sum

APPROACH

Given an array of distinct integers candidates and a target, return all unique combinations of candidates that sum to target. Each candidate may be reused any number of times. Two combinations differ if any element has a different frequency. The count of valid combinations is below 150.

Example 1:

Input: candidates = [2,3,6,7], target = 7

Output: [[2,2,3],[7]]

Explanation:

2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.

7 is a candidate, and 7 = 7.

These are the only two combinations.

Example 2:

Input: candidates = [2,3,5], target = 8

Output: [[2,2,2,2],[2,3,3],[3,5]]

Example 3:

Input: candidates = [2], target = 1

Output: []

1 of 4

1:00

What is the optimal approach for this problem?