CODEWITHSUNDEEP
javamathdata-structuresintegersubset-sum
crackerplace
crackerplace

Reputation: 5475

Subsets of a given Set of Integers whose sum is a Constant N : Java

Given a set of integers, how to find a subset that sums to a given value...the subset problem ?

Example : S = {1,2,4,3,2,5} and n= 7 Finding the possible subsets whose sum is n. I tried to google out found many links,but were not clear. How can we solve this in java and what is the data structure to be used and its complexity ?

Upvotes: 0

Views: 2849

Answers (2)

ase
ase

Reputation: 13481

In three steps:

  1. Find the powerset of S (the set of all subsets of S)

  2. Compute the sum of each subset

  3. Filter out subsets that did not sum to 7.

Upvotes: 2

Shamim Hafiz - MSFT
Shamim Hafiz - MSFT

Reputation: 22114

I wont give you any code, but explain how it works.

  1. Run a loop from 0 to (2^k-1)
  2. For each value in 1, a 1 in its binary representation indicates that this value is chosen and 0 otherwise.
  3. Test to see if the sum of chosen numbers is equal to n.

The above method will evaluate each possible subset of the given set.

If the upper limit of the values is small, then Dynamic Programming Approach could be used.

Upvotes: 1

Related Questions