Mark As Completed Discussion

Good evening! Here's our prompt for today.

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.

Question

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

SNIPPET
1candidates = [2, 3, 5] and target = 9
2
3Output: [[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

SNIPPET
1candidates = [5, 2, 7] and target = 1
2
3Output: []

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

SNIPPET
1candidates = [2, 3, 6, 7] and target = 7
2
3Output: [[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.

Try to solve this here or in Interactive Mode.

How do I practice this challenge?

JAVASCRIPT
OUTPUT
:001 > Cmd/Ctrl-Enter to run, Cmd/Ctrl-/ to comment

Here's how we would solve this problem...

How do I use this guide?

Access all course materials today

The rest of this tutorial's contents are only available for premium members. Please explore your options at the link below.

Returning members can login to stop seeing this.