39. Combination Sum

Medium

16K

320

Given an array of **distinct** integers `candidates`

and a target integer `target`

, return *a list of all unique combinations of *

`candidates`

`target`

The **same** number may be chosen from `candidates`

an **unlimited number of times**. Two combinations are unique if the

The test cases are generated such that the number of unique combinations that sum up to `target`

is less than `150`

combinations for the given input.

**Example 1:**

Input:candidates = [2,3,6,7], target = 7Output:[[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 = 8Output:[[2,2,2,2],[2,3,3],[3,5]]

**Example 3:**

Input:candidates = [2], target = 1Output:[]

**Constraints:**

`1 <= candidates.length <= 30`

`2 <= candidates[i] <= 40`

- All elements of
`candidates`

are**distinct**. `1 <= target <= 40`

Accepted

1.5M

Submissions

2.1M

Acceptance Rate

68.9%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved