The target sum problem requires you to find a subset of numbers that adds up to a target number. This is a common DSA interview problem on arrays, and we have solved this using brute force.
Given a set of integers and a target value k, find whether there is a non-empty subset that sums up to k.
{
"arr": [2, 4, 8],
"k": 6
}
Output:
1
Because 2 + 4 = 6.
{
"arr": [2, 4, 6],
"k": 5
}
Output:
0
Because no subset of numbers from the input sums up to 5.
Constraints:
k <= 1012If 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 2n.
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 have provided a solution that uses this idea.
O(2n).
Each call of the recursive function makes exactly two more calls until the depth of recursion reaches n. Total number of calls is therefore 2n. 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(2n).
O(n).
O(n) due to the function call stack: the greatest recursion depth would be n and each stack frame uses constant space.
O(n).
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 the constraints given to us, n * k can be as big as 18 * 1012. That is a much greater number than 2n, which is at worst 218 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:
n <= 10000k <= 100Then O(n * k) becomes much better than O(2n) in the worst case: 106 << 210000.
/*
* Asymptotic complexity in terms of size of \`arr\` \`n\`:
* Time: O(2^n).
* Auxiliary space: O(n).
* Total space: O(n).
*/
bool check(int start, int n, vector<long long int> &arr, long long int remaining,
bool at_lest_one_included)
{
if (start >= n)
{
// Remaining sum should be 0 and we should have included at least one number!
return remaining == 0 && at_lest_one_included;
}
/*
We are not including current element. So at_lest_one_included will be dependent on previous
elements.
*/
if (check(start + 1, n, arr, remaining, at_lest_one_included))
{
return true;
}
/*
Include the current element. Now we have included at least one element so
at_lest_one_included should be true.
*/
return check(start + 1, n, arr, remaining - arr[start], true);
}
bool check_if_sum_possible(vector<long long> &arr, long long k)
{
return check(0, arr.size(), arr, k, false);
}
We hope that these solutions to achieving target sum problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.
If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart’s FREE webinar to understand the best way to prepare.
Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.
We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:
To learn more, register for the FREE webinar.
