All problems

Combination Sum

Medium · backtracking

Given a list candidates of distinct positive integers and a positive integer target, return every combination of candidates that adds up to target. You may use the same number as many times as you like.

To make the answer unique, write each combination in ascending order (for example [2, 2, 3], never [3, 2, 2]). Two combinations are different if they use some number a different number of times. The combinations may be returned in any order. If no combination reaches target, return an empty list.

Examples

Example 1

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

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

2 + 2 + 3 = 7, using the 2 twice. 7 alone also works. Nothing else adds up to 7.

Example 2

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

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

[3, 2, 3] is the same combination as [2, 3, 3], so it is only listed once, in ascending order.

Example 3

Input: candidates = [2], target = 1

Output: []

The smallest candidate is 2, which already overshoots 1.

Constraints