Thread: Sum Subsets

Hi everyone, first time on this forum and I'm thrilled. I was wondering if anyone could perhaps show me where I can find an article, formula, book, etc, that tells me what I want to find below.

You have a number n and a list of numbers. I want to generate all the different combinations from the list that add up the n.
Example.

n = 4;
list = [1,2]

Combination 1: 1 + 1 + 1 + 1 = 4
Combination 2: 1 + 1 + 2 = 4
Combination 3: 2 + 2 = 4

There are 3 different combinations that sum up to 4 from the given list.

n = 6
list = [1,3,6]

Combination 1: 1+1+1+1+1+1 = 6
Combination 2: 1+1+1+3 = 6
Combination 3: 3+3 = 6
Combination 4: 6=6

There are 4 different combinations that sum up to 6 from the given list.

Is there an algorithm or something that I can use in a java program that will accomplish this?

Thank you.

I think what you're looking for might be called: enumeration of partitions (only you restricted to a base list, not all integers). Maybe that will help you hunt for this. I'd be shocked if there weren't a LOT of theory and/or code for exactly this. It wouldn't surprise me if exactly what you're requesting doesn't already exist as a routine in one of the major math software packages. However, I don't know of it - that's just a guess. If you're at a university, you might want to ask a professor, especially a comp sci professor or math professor.

There are various recurrsive algorithms: Here's one off the top of my head, where you shrink down your choice list in one part and the size of your sum in the other. I've no idea if this is a good approach - I'm offering it up to give you some ideas.

ResultList (SumsTo=N; Uses=ChoiceList; RunningAppendList)
=
(Pick a k in the incoming ChoiceList)
ResultList (SumsTo=N-k; Uses=ChoiceList; RunningAppendList.AppendWith(k))
UNION
ResultList (SumsTo=N; Uses=ChoiceList.Remove(k); RunningAppendList)