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

# Recursive function to test all combinations?

Page 1 of 1## 5 Replies - 805 Views - Last Post: 17 May 2014 - 09:26 PM

##
**Replies To:** Recursive function to test all combinations?

### #2

## 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

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

## 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.

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

## 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

## 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

EDIT: bloody formatting tags. please disregard the gratuitous backslash

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

## 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??

Page 1 of 1