Possible To Achieve Target Sum Problem

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

Solutions

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.

// -------- START --------

/*
Note that we are passing arr by reference. Either pass by reference or use global variable.
Passing by value will slow down the solution.
*/
bool check(int start, int n, vector &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 arr, long long int k)
{
    return check(0, arr.size(), arr, k, false);
}

// -------- END --------

Additional observations:

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.