CODEWITHSUNDEEP
dynamic-programming
Ricardo
Ricardo

Reputation: 345

Get all possible sums from a list of numbers

Let's say I have a list of numbers: 2, 2, 5, 7

Now the result of the algorithm should contain all possible sums.

In this case: 2+2, 2+5, 5+7, 2+2+5, 2+2+5+7, 2+5+7, 5+7

I'd like to achieve this by using Dynamic Programming. I tried using a matrix but so far I have not found a way to get all the possibilities.

Upvotes: 3

Views: 14667

Answers (4)

risingStark
risingStark

Reputation: 1155

I have a solution that can print a list of all possible subset sums. Its not dynamic programming(DP) but this solution is faster than the DP approach.

void solve(){
    ll i, j, n;
    cin>>n;
    vector<int> arr(n);
    const int maxPossibleSum=1000000;
    for(i=0;i<n;i++){
        cin>>arr[i];
    }
    bitset<maxPossibleSum> b;
    b[0]=1;
    for(i=0;i<n;i++){
        b|=b<<arr[i];
    }
    for(i=0;i<maxPossibleSum;i++){
        if(b[i])
            cout<<i<<endl;
    }
}

Input:
First line has the number of elements N in the array.
The next line contains N space-separated array elements.
4
2 2 5 7

----------
Output:
0
2
4
5
7
9
11
12
14
16

The time complexity of this solution is O(N * maxPossibleSum/32)
The space complexity of this solution is O(maxPossibleSum/8)

Upvotes: 0

Bill Bell
Bill Bell

Reputation: 21663

This is not an answer to the question because it does not demonstrate the application of dynamic programming. Rather it notes that this problem involves multisets, for which facilities are available in Sympy.

>>> from sympy.utilities.iterables import multiset_combinations
>>> numbers = [2,2,5,7]
>>> sums = [ ]
>>> for n in range(2,1+len(numbers)):
...     for item in multiset_combinations([2,2,5,7],n):
...         item
...         added = sum(item)
...         if not added in sums:
...             sums.append(added)
...             
[2, 2]
[2, 5]
[2, 7]
[5, 7]
[2, 2, 5]
[2, 2, 7]
[2, 5, 7]
[2, 2, 5, 7]
>>> sums.sort()
>>> sums
[4, 7, 9, 11, 12, 14, 16]

Upvotes: 0

User_Targaryen
User_Targaryen

Reputation: 4225

Based on the question, I think that the answer posted by AT-2016 is correct, and there is no solution that can exploit the concept of dynamic programming to reduce the complexity.

Here is how you can exploit dynamic programming to solve a similar question that asks to return the sum of all possible subsequence sums.

Consider the array {2, 2, 5, 7}: The different possible subsequences are:

{2},{2},{5},{7},{2,5},{2,5},{5,7},{2,5,7},{2,5,7},{2,2,5,7},{2,2},{2,7},{2,7},{2,2,7},{2,2,5}

So, the question is to find the sum of all these elements from all these subsequences. Dynamic Programming comes to the rescue!!

Arrange the subsequences based on the ending element of each subsequence:

  1. subsequences ending with the first element: {2}
  2. subsequences ending with the second element: {2}, {2,2}
  3. subsequences ending with the third element: {5},{2,5},{2,5},{2,2,5}
  4. subsequences ending with the fourth element: {7},{5,7},{2,7},{2,7},{2,2,7},{2,5,7},{2,5,7},{2,2,5,7}.

Here is the code snippet:

The array 's[]' calculates the sums for 1,2,3,4 individually, that is, s[2] calculates the sum of all subsequences ending with third element. The array 'dp[]' calculates the overall sum till now. 

 s[0]=array[0];
 dp[0]=s[0];
 k = 2;
 for(int i = 1; i < n; i ++)
 {
    s[i] = s[i-1] + k*array[i];
    dp[i] = dp[i-1] + s[i];
    k = k * 2;
 }
 return dp[n-1];

Upvotes: 4

AT-2017
AT-2017

Reputation: 3149

This is done in C# and in an array to find the possible sums that I used earlier:

static void Main(string[] args)
{
    //Set up array of integers
    int[] items = { 2, 2, 5, 7 };

    //Figure out how many bitmasks is needed

    //4 bits have a maximum value of 15, so we need 15 masks.
    //Calculated as: (2 ^ ItemCount) - 1
    int len = items.Length;
    int calcs = (int)Math.Pow(2, len) - 1;

    //Create array of bitmasks. Each item in the array represents a unique combination from our items array
    string[] masks = Enumerable.Range(1, calcs).Select(i => Convert.ToString(i, 2).PadLeft(len, '0')).ToArray();

    //Spit out the corresponding calculation for each bitmask
    foreach (string m in masks)
    {
        //Get the items from array that correspond to the on bits in the mask
        int[] incl = items.Where((c, i) => m[i] == '1').ToArray();

        //Write out the mask, calculation and resulting sum
        Console.WriteLine(
            "[{0}] {1} = {2}",
            m,
            String.Join("+", incl.Select(c => c.ToString()).ToArray()),
            incl.Sum()
        );
    }

    Console.ReadKey();
}

Possible outputs:

[0001] 7 = 7
[0010] 5 = 5
[0011] 5 + 7 = 12
[0100] 2 = 2

Upvotes: 2

Related Questions