• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Paul Clapham
  • Jeanne Boyarsky
Sheriffs:
  • Ron McLeod
  • Frank Carver
  • Junilu Lacar
Saloon Keepers:
  • Stephan van Hulst
  • Tim Moores
  • Tim Holloway
  • Al Hobbs
  • Carey Brown
Bartenders:
  • Piet Souris
  • Frits Walraven
  • fred rosenberger

Finding all the possible sums in an array using recursion

 
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Problem:

The problems also states that there may be duplicates.

Here is an example to go by.

Array = {1, 2, 4, 5}

Possible Sums: 0, 1, 2, 4, 5, 3, 5, 6, 6, 7, 7, 8, 9, 10, 11 and 12

6 appears twice because 2+4 and 1+5 equals 6

The order in the array is irrelevant


Possible but impractical solution:

The first idea that came to mind, like in any recursion problem, is to continuously break down the array until it is has only one element available and then backtrack from there. From what I can tell, this solution has a big oh 2^n complexity and here is why I think so. Let's use the Array = {1, 2, 4, 5} as an example and what we are going to do is break it up into sub arrays eg. {1}, {1,2} etc.

{1} takes 1 operation
{1,2} takes 2 operation because you have already done 1 and what's left is 2 and 2 + 1.
{1,2,4} takes 4 operation using the same reasoning that I used above.
{1,2,4,5} Finally this sub array will take 8 operations.

So from this analysis, the time complexity for this appears to be 2^n which is very bad. Can you think of another way to improve this?
 
lewis manuel
Ranch Hand
Posts: 64
2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Here is some code that I created using recursion and it works perfectly. Whether if it's good or not remains to be seen but at least I was able to make the method short and concise.

 
Bartender
Posts: 5067
189
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
hi Lewis,

I was still thinking about what Winston and Carey wrote in your other topic.
But this one: I think it is O(2^n), can't improve on that.
Think of generating all possible subsets of a set of N. Including the
empty set, there are 2^N of 'm. Each having its own sum.

So, you can also try to write a recursive routine that determines
all subsets, and map each of these to its sum. That will give you an excellent
way to test you present method.

I wrote one myself some time ago. The problem was the classic water pouring
problem. Given N glasses of certain volumes, can you generate a certain
volume by filling, emptying and pouring the avalilable glasses?
I wanted to solve the problem that a certain combination of the glasses,
when summing their volumes, would give the required volume.
I did that by indeed creating all subsets and see if any sum would equal
the target.

Maybe a nice idea for the next puzzle?
 
Marshal
Posts: 27371
88
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

lewis manuel wrote:So from this analysis, the time complexity for this appears to be 2^n which is very bad. Can you think of another way to improve this?



You want the sums of all subsets of a set with N elements? There are 2^N such subsets, as your analysis confirms. So given that any algorithm is going to have to do at least one operation to produce each of the sums, it's going to have to do at least 2^N operations.

I thought up an algorithm which isn't recursive, but after I looked at your code I realized it was pretty similar to yours. However for a non-recursive algorithm you'd have to store the sums in a list rather than just printing them, as you do.
 
Marshal
Posts: 76450
366
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Storing results in a List may give faster execution than multiple print statements.
 
It sure was nice of your sister to lend us her car. Let's show our appreciation by sharing this tiny ad:
Garden Master Course kickstarter
https://coderanch.com/t/754577/Garden-Master-kickstarter
reply
    Bookmark Topic Watch Topic
  • New Topic