#39

Combination Sum

pupil · 475 · lc medium +27 · verified · 76.2% accepted · 20,878 likes · top 87%

Description

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: []

Code

1

2

3

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:

class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]: