Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Finding all possible sums of a set

Tags:

java

arrays

set

I am currently looking for ideas on how to find all possible sums of a set of numbers with these rules. I have these numbers to work with and I want to find all possible sums so that you can only use a single number at max 4 times and each time you pick 7 of these numbers.

{ 0, 1, 5, 22, 98, 453, 2031, 8698, 22854, 83661, 262349, 636345 and 1479181 }

Acceptable examples would be

0 + 0 + 0 + 0 + 83661 + 83661 + 2031

Unacceptable example would be

0 + 0 + 0 + 0 + 0 + 83661 + 2031

The only way I can think of is a series of nested loops but I am having trouble with that as well. Would there be any other options to do this. I am using Java but I don't really think that matters.

like image 455
user3070528 Avatar asked Oct 01 '22 03:10

user3070528


1 Answers

You can achieve this by building a new List of elements that contains each element of the given set duplicated 4 times . then use a DFS strategy method to build possible possible sum combination. to have an idea about how to implement DFS check this answer

like image 55
Mifmif Avatar answered Nov 10 '22 21:11

Mifmif