Subset Sum CLRS 35.5, Part 2

May 30, 2014

In the previous exercise we implemented the subset sum algorithms of CLRS 35.5. In today’s exercise we solve exercise 35.5-5, which asks us to return the subsets as well as their sums. The algorithm is exactly the same. The difference is that set members are stored along with their partial sums.

Your task is to write a program that solves the subset sum problem as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

One Response to “Subset Sum CLRS 35.5, Part 2”

  1. […] though the meet-in-the-middle solution has better asymptotic time of O(n2n/2). We also studied a solution that takes polynomial time to produce an approximate answer to the subset sum problem, although […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: