Count combinations of positive and negative that sum to target number

Question

The problem I'm solving is given as follows:

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S.

Here is my solution:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        return findTargetSum(nums, 0, S, 0);
    }

    int findTargetSum(vector<int>& nums, int i , int S, int sumSoFar){
        if(i == nums.size()){
            return sumSoFar == S;
        }

        return findTargetSum(nums, i + 1, S, sumSoFar + nums[i]) + findTargetSum(nums, i + 1, S, sumSoFar - nums[i]);
    }
};

This solution however performs slower than the target. I suspect there may be some DP solution I am missing or maybe some optimization in my current solution might be to blame. Any advice on how to cut the run time would be appreciated.

Answer 1

One improvement would be to, at the start:

1. Sort the list (largest first)
2. For each index, record the sum of everything after that index

Then while recursing, you can fail out early if at any point the delta between the current sum and the goal is greater than the sum of the remaining elements.

Answer 2

The question as asked by OP left out one crucial piece of information: The constraints of the problem. Listed below:

Note: The length of the given array is positive and will not exceed 20. The sum of elements in the given array will not exceed 1000. Your output answer is guaranteed to be fitted in a 32-bit integer.

And herein lies a big hint: The sum of all elements will not exceed 1000 (and all input values are positive). This is the creators of the problem telling you that you can trade fixed size memory for speed, which wouldn't be possible if this constraint was not present.

Note that that "The result will fit in a 32 bit integer" is redundant and over estimated, as there can be max 20 elements only 2^20 combinations of +- exist and thus only 20 bits are needed to store the result, incidentally this means that you only need to try 1 million combinations of +- to brute force the problem which shouldn't take much more than 20 numbers*1 million combinations*instructions per number, which would be at most a second or so on a modern machine unless you botch the implementation.

Because addition and subtraction commutes you can sort the array without affecting the result. The individual solutions may change but not the number of solutions. This together with bounding of the largest possible remaining sum can be used to prune some branches from the search to improve upon brute force.

In general, the constraints are such that the brute force solution implemented efficiently should be enough, but we can do better if we use some memory.

Imagine an array A which can be indexed by values -1000 to 1000 (just offset the index by +1000 in your code, mapping the range -1000...1000 to 0...2000).

Then, for each index I we store a value V which is how many ways we can compute a sum of I. So when we are done, the answer to the problem: "In how many ways can you assign +- to the input values so that their sum in S", will be A[S].

Pseudo-code:

1. Create two arrays A and B, indexable from -1000 to 1000 and set all elements to 0.
2. Take the first value from the input, call it: a
3. And set A[a] = 1 and A[-a] = 1
4. Take the next value from the input, call it: b
5. For every index i, where A[i] is non-zero do: B[i+b] += A[i], B[i-b] += A[i], A[i] = 0
6. Swap A and B
7. Repeat from 4 until no more input is available
8. Return A[S]

The above procedure will take 20 iterations of 4. to 7. with the maximum problem size. Step 5 requires a scan through A meaning 2000 loop iterations. So all in all for the max problem size 40k iterations of the inner most loop are needed. Lets estimate the inner loop body to be 10 instructions putting us at around 400k instructions which is around two orders of magnitude less than brute force.

The observant reader will note that there is a lot of wasted time in scanning through A in step 5 to find the non-zero entries. There is a way to avoid this by using an auxiliary array to store non-zero indexes for the next iteration to speed this up. The details of this are left as an exercise for the reader.

There is another optimisation that can be made to get rid of the cost of offsetting the indexes in the inner most loop, can you find it?

Answer 3

Headers

I needed to add

#include <vector>
using std::vector;

to make this code compile

Algorithm

Recursion is usually a poor choice in C++ when a simple loop would work instead. Since you're exhaustively enumerating the possibilities, note that your selection of + or - n times is equivalent to iterating over the binary numbers from 0 to 2^n - 1. So you could break the list into chunks matching the bit-width of your largest available unsigned type and reduce the recursion depth that way.

We might be able to reduce the size of the problem with some mathematical insight: if we can find subsets that sum to zero, you might be able to use them to reduce the search space (as the complement of that subset also sums to zero).

Style

Don't pass containers by value if you don't intend to modify the contents; pass a const reference instead, or (better) a pair of const_iterator.

Match the type of i to the result type of nums.size() - in this case std::size_t (from <cstddef>).

If we break the last return over two lines, the symmetry of the algorithm becomes more apparent:

    return findTargetSum(nums, i + 1, S, sumSoFar + nums[i])
        +  findTargetSum(nums, i + 1, S, sumSoFar - nums[i]);

Also, if we re-order the arguments, we can default i and sumSoFar, thus needing only a single function:

int findTargetSumWays(const std::vector<int>& nums, int S,
                      std::size_t i = 0, int sumSoFar = 0)
{
    if (i == nums.size()) {
        return sumSoFar == S;
    }

    return findTargetSumWays(nums, S, i + 1, sumSoFar + nums[i])
        +  findTargetSumWays(nums, S, i + 1, sumSoFar - nums[i]);
}

Answer 4

This can be solved as a graph problem using any graph search algorithm such as DFS, or my favorite, iterative deepening DFS (IDDFS). You can use BFS, but you will end up running out of memory if the list of numbers is sufficiently large.

Preparation:

• Choose a graph search algorithm
• You will start with an empty graph and build it up as you progress with the search.
• The nodes in your graph consist of a set of (value, operator) pairs

Implementation

• To begin, your root node contains the number zero.
• The successors of the current node are made of nodes containing some (value, operator) pair that is not already in the current node. Make sure to consider all combinations (ex. +2, -2, +3, -3)
• Your goal is that the sum of the values in the current node sum up to the target S
• Your goal is that the sum of the values in the current node sum up to the target S, but you keep running the algorithm until you have run out of nodes

Doing it this way, you build the graph as you search it.

As long as you make sure not to repeat the digits used to create a node, you will be guaranteed to find a solution quickly or quickly find that there is no solution