Count combinations of positive and negative that sum to target number 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&lt;int&gt;&amp; nums, int S) {
        return findTargetSum(nums, 0, S, 0);
    }

    int findTargetSum(vector&lt;int&gt;&amp; 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.
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:


Create two arrays A and B, indexable from -1000 to 1000 and set all elements to 0.
Take the first value from the input, call it: a
And set A[a] = 1 and A[-a] = 1
Take the next value from the input, call it: b
For every index i, where A[i] is non-zero do: B[i+b] += A[i], B[i-b] += A[i], A[i] = 0
Swap A and B
Repeat from 4 until no more input is available
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?