School Assignment? Project Due Tomorrow? Chat LIVE With A Programming Expert!

Welcome to Dream.In.Code
Become an Expert!

Join 307,175 Programmers for FREE! Get instant access to thousands of experts, tutorials, code snippets, and more! There are 1,553 people online right now. Registration is fast and FREE... Join Now!




Subset sums

 

Subset sums

airwizard

8 Feb, 2009 - 03:27 AM
Post #1

New D.I.C Head
*

Joined: 1 Feb, 2009
Posts: 3

The problem is the following:

You are given a set of positive integers { a1 , a2 , a3 , ... , an } in which there are no same numbers ( a1 exists only once ,a2 exists only once,...) eg A = {12 , 5 ,7 ,91 }.
Question: Are there two disjoint subsets of A , A1 = { b1,b2,...,bm } and A2 = { c1,c2,...,ck} so that b1+b2+...+bm = c1+c2+...+ck ?

Note the following: It is not obligatory for A1 and A2 to cover A, so the problem isn't automatically reduced to the subset sum problem.
eg A = {2,5,3,4,8,12}
A1= {2,5} so sum of A1 is 7
A2= {3,4} so sum of A2 is 7
We found two disjoint subsets of A with the described property so the problem is solved.

How can I solve this problem? Can I do something better than find all possible (disjoint)subsets, calculate their sums and find two equal sums?

Thank you for your time.I am not asking this in order to get code(after all it is an algorithmic question) but in order to know the complexity of this problem and if it can be reduced to a known problem.

User is offlineProfile CardPM
+Quote Post

 
Reply to this topicStart new topic
Replies(1 - 1)

Gloin

RE: Subset Sums

9 Feb, 2009 - 04:34 PM
Post #2

Expert Schmexpert...
Group Icon

Joined: 4 Aug, 2008
Posts: 3,614



Thanked: 143 times
Dream Kudos: 75
My Contributions
The Subset sum problem is an NPC problem and it appears to me that the same goes for the given problem as it has the same characteristics as the Subset sum problem.
User is offlineProfile CardPM
+Quote Post

Fast ReplyReply to this topicStart new topic

Time is now: 11/21/09 07:28PM

Live Help!

Be Social

Dream.In.Code RSS Feed Dream.In.Code LinkedIn Group Follow Us On Twitter Fan Us On Facebook

Tutorials

Programming

Web Development

Reference Sheets

Code Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month