Combination Sum

candidates are different positive whole numbers. Return every different combination of them that adds up to target, where each candidate can be used any number of times. Write each combination in increasing order, and list the combinations in dictionary order.

For candidates = [2, 3, 6, 7] and target = 7: [2, 2, 3] and [7].

Examples

Example 1

Input:

combination_sum([2, 3, 6, 7], 7)

Output:

[[2, 2, 3], [7]]

Example 2

Input:

combination_sum([2], 1)

Output:

[]

Constraints

• 0 <= len(candidates) <= 8
• 1 <= candidates[i] <= 30, all different
• 1 <= target <= 40