Sub-sum problem (NP)

This is a discussion on Sub-sum problem (NP) within the C Programming forums, part of the General Programming Boards category; Hi, I'm new here but after googling a whole day, I couldn't find another solution then to ask you guys ...

  1. #1
    Registered User
    Join Date
    Aug 2008
    Posts
    2

    Sub-sum problem (NP)

    Hi,
    I'm new here but after googling a whole day, I couldn't find another solution then to ask you guys on this forum about some help for my problem.
    I believe it's more advanced type of sub-sum problems. More advanced because sub-summing is limited only to '+' operations, here I have both, the '+' and '-' operations.
    Here's the problem itself:
    ---
    A set of natural numbers is given. Generate all the subsets of this set joined by alternating + and - operators which
    sum up to exactly S. .
    I/O description. Input: enumeration of elements in the set, on one line, then sum on one line e.g.
    1 3 5 7 2 6
    0
    Output: enumeration of elements resulting in the given sum, e.g.
    1-3+2
    1+3-6
    5-7+2
    1+5-6
    ...
    ---

    I thought a possible solution would be the generation of a matrice(table) in wich I would start placing 1 or -1 or 0 for each cell. But I didn't succed at all.
    I thought maybe someone already had to deal with such a problem, but on the web I cound't find it's solution...
    Thank you in advance...

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by stass View Post
    I thought a possible solution would be the generation of a matrice(table) in wich I would start placing 1 or -1 or 0 for each cell. But I didn't succed at all.
    You would need to add in the condition that you must have either the same numbers of 1's and -1's, or one more 1 than -1 (since we'll always add before we subtract).

    That will help cut down on the number of 1/0/-1 combinations you would have to check. I don't know of any reasonably efficient other method.

  3. #3
    Registered User
    Join Date
    Aug 2008
    Posts
    2

    Thank you tabstop, at least I'm on the right way.
    Regards.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Minor Problem
    By stewie1986 in forum C Programming
    Replies: 6
    Last Post: 11-30-2007, 08:40 AM
  2. a sum equal to or in excess of 100
    By lyoncourt in forum C Programming
    Replies: 6
    Last Post: 10-07-2007, 06:43 PM
  3. ?? with trying to sum numbers
    By Babs21 in forum C Programming
    Replies: 1
    Last Post: 09-16-2007, 04:58 PM
  4. Bin packing problem....
    By 81N4RY_DR460N in forum C++ Programming
    Replies: 0
    Last Post: 08-01-2005, 06:20 AM
  5. string to int conversion not using atoi()
    By linucksrox in forum C Programming
    Replies: 2
    Last Post: 05-19-2004, 01:17 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21