Given a set of integers and a target value k, find a non-empty subset that sums up to k.
Input: [2 4 8], k = 6
Input: [2 4 6], k = 5
Because no subset of numbers from the input sums up to 5.
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.
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:
This pattern can be helpful to solve the problem!
Let us now take n = 4:
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:
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.
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.
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.