Results 1 to 2 of 2

Math Help - Sum Subsets

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    LA
    Posts
    2

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

  2. #2
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    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))
    UNION
    ResultList (SumsTo=N; Uses=ChoiceList.Remove(k); RunningAppendList)
    Last edited by johnsomeone; September 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: August 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: December 29th 2010, 10:33 AM
  4. Subsets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: October 31st 2009, 12:48 AM
  5. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2009, 07:54 PM

Search Tags


/mathhelpforum @mathhelpforum