5 Replies - 242 Views - Last Post: 17 May 2014 - 09:26 PM Rate Topic: -----

#1 JavaSuperNoob  Icon User is offline

  • D.I.C Head

Reputation: -1
  • View blog
  • Posts: 57
  • Joined: 13-February 12

Recursive function to test all combinations?

Posted 17 May 2014 - 07:33 PM

I am not sure how to add all the possibilities of elements in an array and find the greatest sum. A little pointer would be of help. I want to do this recursively. I don't need any code. Just ideas as to how I would do it. Thank you very much
Is This A Good Question/Topic? 0
  • +

Replies To: Recursive function to test all combinations?

#2 infernorthor  Icon User is offline

  • D.I.C Addict

Reputation: 187
  • View blog
  • Posts: 876
  • Joined: 07-February 14

Re: Recursive function to test all combinations?

Posted 17 May 2014 - 07:49 PM

There are many ways to do it. I'm not sure of much you understand combinatorics. Reading about that may help.

In programming you either solve a problem with algorithms or equations. Algorithms sometimes are easier to figure out, but take longer to compute. While equation may be hard to figure what equation to use, but execute really fast.

For this, could you figure how many sums would be created? And if numbers repeat sums would also repeat.

like 1 1 2
sum of 2 would give:
1+1 = 2
1+2 = 3
1+2 = 3
3 sums but only 2 unique sums
Was This Post Helpful? 0
  • +
  • -

#3 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7629
  • View blog
  • Posts: 12,858
  • Joined: 19-March 11

Re: Recursive function to test all combinations?

Posted 17 May 2014 - 08:01 PM

Start by thinking of a dumb answer that ought to work - don't worry about whether it's the best answer or not, just come up with something that you think does the job.
When you've done that, you're in a position to think about how to do it better, but you should always start with something that solves the problem, at least in a small instance.
Was This Post Helpful? 1
  • +
  • -

#4 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10445
  • View blog
  • Posts: 38,682
  • Joined: 27-December 08

Re: Recursive function to test all combinations?

Posted 17 May 2014 - 09:12 PM

Clearly you want to ignore negative numbers. You can ignore elements valued at 0 as well. So you're only interested in strictly positive elements of the array. Sort the array, start from the end, then run a sum until you hit a non-positive number.
Was This Post Helpful? 0
  • +
  • -

#5 jon.kiparsky  Icon User is online

  • Pancakes!
  • member icon


Reputation: 7629
  • View blog
  • Posts: 12,858
  • Joined: 19-March 11

Re: Recursive function to test all combinations?

Posted 17 May 2014 - 09:23 PM

Hm. I was assuming that you wanted the sequence producing the greatest possible sum. That is, the indices i,j such that maximize sum(arr[\i], arr[i+1], ... arr[j]). If that's the case, then clearly it's not quite as simple as mac's making it out to be.

Example:
[1, 9, 0, 0, -1, 9]

Clearly the sequence producing the greatest sum is just the whole thing, notwithstanding the zero and negative elements.

However, it's almost as simple. See if you can work out the slight modification to mac's idea that does the job.

EDIT: bloody formatting tags. please disregard the gratuitous backslash

This post has been edited by jon.kiparsky: 17 May 2014 - 09:25 PM

Was This Post Helpful? 0
  • +
  • -

#6 infernorthor  Icon User is offline

  • D.I.C Addict

Reputation: 187
  • View blog
  • Posts: 876
  • Joined: 07-February 14

Re: Recursive function to test all combinations?

Posted 17 May 2014 - 09:26 PM

Why would you ignore 0 or negative numbers? And that shouldn't be implementing in a general algorithm. You can add negative numbers. What if they are all negative??
Was This Post Helpful? 1
  • +
  • -

Page 1 of 1