CODEWITHSUNDEEP
c++algorithmmath
tuxikigo
tuxikigo

Reputation: 23

Every sum possibilities of elements

From a given array (call it numbers[]), i want another array (results[]) which contains all sum possibilities between elements of the first array.

For example, if I have numbers[] = {1,3,5}, results[] will be {1,3,5,4,8,6,9,0}. there are 2^n possibilities. It doesn't matter if a number appears two times because results[] will be a set

I did it for sum of pairs or triplet, and it's very easy. But I don't understand how it works when we sum 0, 1, 2 or n numbers.

This is what I did for pairs :

std::unordered_set<int> pairPossibilities(std::vector<int> &numbers) {
    std::unordered_set<int> results;
    for(int i=0;i<numbers.size()-1;i++) {
        for(int j=i+1;j<numbers.size();j++) {
            results.insert(numbers.at(i)+numbers.at(j));
        }
    }
    return results;
}

Also, assuming that the numbers[] is sorted, is there any possibility to sort results[] while we fill it ?

Thanks!

Upvotes: 1

Views: 312

Answers (4)

Gem Taylor
Gem Taylor

Reputation: 5635

There has to be a binary chop version, as well. This one is a bit heavy-handed and relies on that set of answers you mention to filter repeated results:

Split the list into 2,  
and generate the list of sums for each half 
  by recursion:
    the minimum state is either 
      2 entries, with 1 result, 
      or 3 entries with 3 results
      alternatively, take it down to 1 entry with 0 results, if you insist
Then combine the 2 halves:
  All the returned entries from both halves are legitimate results
  There are 4 additional result sets to add to the output result by combining:
    The first half inputs vs the second half inputs
    The first half outputs vs the second half inputs
    The first half inputs vs the second half outputs
    The first half outputs vs the second half outputs

Note that the outputs of the two halves may have some elements in common, but they should be treated separately for these combines.
The inputs can be scrubbed from the returned outputs of each recursion if the inputs are legitimate final results. If they are they can either be added back in at the top-level stage or returned by the bottom level stage and not considered again in the combining.

You could use a bitfield instead of a set to filter out the duplicates. There are reasonably efficient ways of stepping through a bitfield to find all the set bits. The max size of the bitfield is the sum of all the inputs.

There is no intelligence here, but lots of opportunity for parallel processing within the recursion and combine steps.

Upvotes: 1

Hello Everyone
Hello Everyone

Reputation: 329

I would do something like this (seems easier) [I wanted to put this in comment but can't write the shifting and removing an elem at a time - you might need a linked list]

1 3 5
3 5
-----
4 8


1 3 5
5
-----
6

1 3 5
3 5
5
------
9

Add 0 to the list in the end.

Another way to solve this is create a subset arrays of vector of elements then sum up each array's vector's data. e.g 1 3 5 = {1, 3} + {1,5} + {3,5} + {1,3,5} after removing sets of single element.

Keep in mind that it is always easier said than done. A single tiny mistake along the implemented algorithm would take a lot of time in debug to find it out. =]]

Upvotes: 1

Samer Tufail
Samer Tufail

Reputation: 1894

Following on from the Dynamic Programming answer, You could go with a recursive solution, and then use memoization to cache the results, top-down approach in contrast to Amit's bottom-up.

vector<int> subsetSum(vector<int>& nums)
{
    vector<int> ans;
    generateSubsetSum(ans,0,nums,0);
    return ans;
}

void generateSubsetSum(vector<int>& ans, int sum, vector<int>& nums, int i)
{
    if(i == nums.size() )
    {
        ans.push_back(sum);
        return;
    }

    generateSubsetSum(ans,sum + nums[i],nums,i + 1);
    generateSubsetSum(ans,sum,nums,i + 1);
}

Result is : {9 4 6 1 8 3 5 0} for the set {1,3,5}

This simply picks the first number at the first index i adds it to the sum and recurses. Once it returns, the second branch follows, sum, without the nums[i] added. To memoize this you would have a cache to store sum at i.

Upvotes: 1

amit
amit

Reputation: 178521

This can be done with Dynamic Programming (DP) in O(n*W) where W = sum{numbers}.

This is basically the same solution of Subset Sum Problem, exploiting the fact that the problem has optimal substructure.

DP[i, 0] = true
DP[-1, w] = false          w != 0
DP[i, w] = DP[i-1, w] OR DP[i-1, w - numbers[i]]

Start by following the above solution to find DP[n, sum{numbers}].

As a result, you will get:

DP[n , w] = true if and only if w can be constructed from numbers

Upvotes: 2

Related Questions