Here is the interview question prompt, presented for reference.

This challenge is all about a well-known problem in programming. You might have come across it in a job interview as part of a test, or even as part of a competition or exam.

The problem is called Combination Sum and there are some variations in how it is presented, but this is the most common one:

Given an array of distinct integer candidates and a goal integer target, you must return all of the unique combinations of the elements whose sum equals target. The order of the combinations does not matter, they just have to be unique.

Note: Two combinations with the same elements in different positions are considered the same. So for example, [2, 2, 3] and [2, 3, 2] are the same combination but [3, 3, 2] is different.

On top of that, any element can be repeated in a combination for an unlimited number of times.

Examples

As stated previously, the output of this program must be all of the unique combinations of elements whose sum is equal to the target. If this seems a bit unclear to you, I’m sure these examples will help. They will just tell you what the output should be for a given array and target.

It should be noted that the array is not sorted but it does not have duplicates.

Example 1

candidates = [2, 3, 5] and target = 9

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

In here you can see that an element is used more than once in all of these combinations. Furthermore, all of these combinations are unique since the frequency of at least one element changes from combination to combination.

Example 2

candidates = [5, 2, 7] and target = 1

Output: []

Sometimes there are no combinations that satisfy the requirement. In this case, this is obvious since the target is smaller than the smallest element of candidates. This, however, isn’t the only case where the output can be empty. For example, the target could be even while the array only has odd numbers or the other way around.

Example 3

candidates = [2, 3, 6, 7] and target = 7

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

This example, like the other ones, gives all of the unique combinations that add up to 7. Any other combination you could come up with would just be one of these but with the elements shuffled around.

You can see the full challenge with visuals at this link.