CODEWITHSUNDEEP
c++algorithm
Arun
Arun

Reputation: 2092

All subsets in Subset_sum_problem

I'm stuck at solving Subset_sum_problem.

Given a set of integers(S), need to compute non-empty subsets whose sum is equal to a given target(T).

Example: Given set, S{4, 8, 10, 16, 20, 22} Target, T = 52.

Constraints: The number of elements N of set S is limited to 8. Hence a NP time solution is acceptable as N has a small upperbound. Time and space complexities are not really a concern.

Output:

Possible subsets with sum exactly equal to T=52 are:

{10, 20, 22}

{4, 10, 16, 22}

The solution given in Wiki and in some other pages tries to check whether there exists such a subset or not (YES/NO).

It doesn't really help to compute all possible subsets as outlined in the above example.

The dynamic programming approach at this link gives single such subset but I need all such subsets.

One obvious approach is to compute all 2^N combinations using brute force but that would be my last resort.

I'm looking for some programmatic example(preferably C++) or algorithm which computes such subsets with illutrations/examples?

Upvotes: 3

Views: 1354

Answers (4)

Ritesh Kumar Gupta
Ritesh Kumar Gupta

Reputation: 5191

The best way to do it is using a dynamic programming approach.However, dynamic programming just answers whether a subset sum exits or not as you mentioned in your question.

By dynamic programming, you can output all the solutions by backtracking.However, the overall time complexity to generate all the valid combinations is still 2^n.

So, any better algorithm than 2^n is close to impossible.

UPD: From @Knoothe Comment: You can modify horowitz-sahni's algorithm to enumerate all possible subsets.If there are M such sets whose sum equals S, then overall time complexity is in O(N * 2^(N/2) + MN)

Upvotes: 1

Alexey Frunze
Alexey Frunze

Reputation: 62048

When you construct the dynamic-programming table for the subset sum problem you intialize most of it like so (taken from the Wikipedia article referenced in the question):

    Q(i,s) := Q(i − 1,s) or (xi == s) or Q(i − 1,s − xi)

This sets the table element to 0 or 1.

This simple formula doesn't let you distinguish between those several cases that can give you 1.

But you can instead set the table element to a value that'd let you distinguish those cases, something like this:

    Q(i,s) := {Q(i − 1,s) != 0} * 1 + {xi == s} * 2 + {Q(i − 1,s − xi) != 0} *4

Then you can traverse the table from the last element. At every element the element value will tell you whether you have zero, one or two possible paths from it and their directions. All paths will give you all combinations of numbers summing up to T. And that's at most 2N.

Upvotes: 2

Mike T
Mike T

Reputation: 4787

Just brute force it. If N is limited to 8, your total number of subsets is 2^8, which is only 256. They give constraints for a reason.

You can express the set inclusion as a binary string where each element is either in the set or out of the set. Then you can just increment your binary string (which can simply be represented as an integer) and then determine which elements are in the set or not using the bitwise & operator. Once you've counted up to 2^N, you know you've gone through all possible subsets.

Upvotes: 1

marcadian
marcadian

Reputation: 2618

if N <= 8 why don't just go with 2^n solution?? it's only 256 possibilities that will be very fast

Upvotes: 2

Related Questions