# Recursive function to test all combinations?

Page 1 of 1

## 5 Replies - 583 Views - Last Post: 17 May 2014 - 09:26 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=347123&amp;s=fe55c8d0784dc91f6d8e60ef43999eb8&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 JavaSuperNoob

Reputation: -1
• Posts: 59
• 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

• D.I.C Lover

Reputation: 362
• Posts: 1,718
• 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

### #3 jon.kiparsky

• Pancakes!

Reputation: 9436
• Posts: 16,361
• 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.

### #4 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11758
• Posts: 44,175
• 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.

### #5 jon.kiparsky

• Pancakes!

Reputation: 9436
• Posts: 16,361
• 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

### #6 infernorthor

• D.I.C Lover

Reputation: 362
• Posts: 1,718
• 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??