Number of ways to add up to a sum S with N numbers

algorithm sum dynamic-programming
Hari Sundararajan picture Hari Sundararajan · Jan 3, 2011 · Viewed 38.1k times · Source

Say S = 5 and N = 3 the solutions would look like - <0,0,5> <0,1,4> <0,2,3> <0,3,2> <5,0,0> <2,3,0> <3,2,0> <1,2,2> etc etc.

In the general case, N nested loops can be used to solve the problem. Run N nested loop, inside them check if the loop variables add upto S.

If we do not know N ahead of time, we can use a recursive solution. In each level, run a loop starting from 0 to N, and then call the function itself again. When we reach a depth of N, see if the numbers obtained add up to S.

Any other dynamic programming solution?

Answer

Mark Byers picture Mark Byers · Jan 3, 2011

Try this recursive function:

f(s, n) = 1                                    if s = 0
        = 0                                    if s != 0 and n = 0
        = sum f(s - i, n - 1) over i in [0, s] otherwise

To use dynamic programming you can cache the value of f after evaluating it, and check if the value already exists in the cache before evaluating it.

Related questions

Google Interview: Find all contiguous subsequence in a given array of integers, whose sum falls in the given range. Can we do better than O(n^2)?

Given an array of Integers, and a range (low, high), find all contiguous subsequence in the array which have sum in the range. Is there a solution better than O(n^2)? I tried a lot but couldn't find a solution …

Read More
Finding minimal absolute sum of a subarray

There's an array A containing (positive and negative) integers. Find a (contiguous) subarray whose elements' absolute sum is minimal, e.g.: A = [2, -4, 6, -3, 9] |(−4) + 6 + (−3)| = 1 <- minimal absolute sum I've started by implementing a brute-force algorithm which was O(N^2) …

Read More
How do I check if an array includes a value in JavaScript?

What is the most concise and efficient way to find out if a JavaScript array contains a value? This is the only way I know to do it: function contains(a, obj) { for (var i = 0; i < a.length; i++) { …

Read More