Our April 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career

Given a set of integers and a target value *k*, find a non-empty subset that sums up to *k*.

**Example One**

Input: [2 4 8], *k* = 6

Output: True

Because 2+4=6.

**Example Two**

Input: [2 4 6], *k* = 5

Output: False

Because no subset of numbers from the input sums up to 5.

**Notes**

Input Parameters: Function has two arguments: an array of integers (their order doesn’t matter) and the target value *k*.

Output: Function must return a boolean value.

**Constraints:**

- 1 <= size of the input array <= 18
- -10^12 <= elements of the array,
*k*<= 10^12

If a solution passes all tests but the test #2, it might be missing one special case: when *k*=0 and there are no zeroes in the array. Correct answer is False in this case. That is because the problem statement asks for “a non-empty subset”. Some similar problems you may find online don’t have the “non-empty” requirement; their solutions will fail our test #2, too.

Now let's think about the solution.

Notice how the array cannot be too big in size: 18 elements maximum. That can suggest that a brute force solution might work well.

We can try to generate all the possible groups (subsets) of the array and see if any of them sums up to *k*. We will remember not to consider empty subsets in the actual program, but much of this editorial counts empty subsets among others for convenience.

Let's consider a few small arrays:

*n* = 1

total number of subsets is 2 (including the empty subset here and below)

*n *= 2

total number of subsets is 4

*n* = 3

total number of subsets is 8

*n* = 4

total number of subsets is 16...

It is easy to observe that the number of distinct subsets we can get from* n* numbers is 2^*n*.

Try to write down all the possible subsets for *n* = 3.

Now use bitmask to represent each subset. For example: if we have taken the second and third elements but not the first, then the bitmask would be 011.

Write down all the bitmasks and sort them:

000

001

010

011

100

101

110

111

This pattern can be helpful to solve the problem!

Let us now take *n* = 4:

0000

0001

0010

0011

0100

0101

0110

0111

1000

1001

1010

1011

1100

1101

1110

1111

Notice how the first 8 bitmasks all start from 0 and last 8 bitmasks all start from 1.

If we remove the first bit from first 8 bitmasks, what remains is this:

000

001

010

011

100

101

110

111

Removing the first bit from the last 8 bitmasks gives the same result. And it happens to be the same pattern we got from* n*=3!

It means that we can choose *not to include* the first element and then generate all the possible subsets for the smaller size (3). Then we can choose to *include* the first element and again generate all the possible subsets for the smaller size (3).

We provided a solution that uses this idea.

**Time Complexity:**

Each call of the recursive function makes exactly two more calls until the depth of recursion reaches *n*. Total number of calls is therefore 2^*n*. Each function call does a constant amount of work (not including work done in the recursive calls it initiates). Overall time complexity is therefore O(2^*n*).

**Auxiliary Space Used:**

O(*n*) due to the function call stack: the greatest recursion depth would be* n* and each stack frame uses constant space.

**Space complexity:**

O(*n*) due to input size and auxiliary space used.

There exists a Dynamic Programming solution to this problem. It is similar to the 0-1 knapsack problem. Its running time is pseudo-polynomial: O(*n***k*).

With constraints given to us *n***k* can be as big as 18*10^12. That is a much greater number than 2^*n* which is at worst 2^18 with the given constraints. So our brute force solution is better for the given constraints.

However if the constraints were different, this could've been a different story. For example if our constraints were

- 1 <=
*n*<= 10000 - -100 <= elements of the array,
*k*<= 100

Then O(*n***k*) becomes much better than O(2^*n*) in the worst case:

10^6 << 2^10000.