Results 1 to 2 of 2

Thread: Sum Subsets

  1. #1
    Sep 2012

    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.

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Sep 2012
    Washington DC USA

    Re: Sum Subsets

    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))
    ResultList (SumsTo=N; Uses=ChoiceList.Remove(k); RunningAppendList)
    Last edited by johnsomeone; Sep 28th 2012 at 07:38 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Subsets (2)
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 18th 2011, 12:17 PM
  2. Subsets of R^3
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: May 14th 2011, 01:26 AM
  3. Subsets
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: Dec 29th 2010, 10:33 AM
  4. Subsets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Oct 31st 2009, 12:48 AM
  5. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 1st 2009, 07:54 PM

Search Tags

/mathhelpforum @mathhelpforum