DIY: Combination Sum

Problem statement

We are given a list of distinct integers named contenders. Our goal is to determine all possible ways to pick any or all of these integers such that they add to the value target. The same number may be picked for addition an unlimited number of times. Two arrangements of numbers that add to target are unique if they differ by at least one number. If two arrangements use the same set of numbers, they are still considered distinct if they differ in the frequency of at least one number.

The order in which these combinations are returned does not matter. Our inputs are guaranteed to be such that the unique arrangements of numbers that add to target wouldn’t exceed 150.

Constraints

• The number of integers in the contenders list will be in the range [1,30].
• Every contender[i] in the contenders list will be in the range of [1,200].
• The values of all the contenders will be unique.
• The amount will be in the range of [1,500].

Input

The first input will be a list of integers called contenders, and the second input will be an integer called target. The following are example inputs:

Input 1:

contenders = [2,3,6,7]
target = 7

Input 2:

contenders = [2,3,5]
target = 8

Input 3:

contenders = [2]
target = 1

Input 4:

contenders = [1]
target = 1

Input 5:

contenders = [1]
target = 2

Output

The output will be a list of lists. These lists will hold all the unique combinations. The followings are sample outputs to the above inputs:

Output 1:

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

Output 2:

[[2,2,2,2],[2,3,3],[3,5]]

Output 3:

[]

Output 4:

[[1]]

Output 5:

[[1,1]]

Coding exercise

You need to implement the function combinationSum(contenders, target) in the skeleton code below.