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:
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
Then O(n*k) becomes much better than O(2^n) in the worst case:
10^6 << 2^10000.