Saturday, September 13, 2014

Subset sum problem.

Subset sum problem. determine if there is a subset of the given set with sum equal to given sum.


Problem statement :-
Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.
Examples: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True //There is a subset (4, 5) with sum 9.

My approach
I do not propose different approach here but helping to understand it. 
Code for approach 2 of Dynamic programming given there is too compact to understand easily. 
So I expanded the steps and added few comments so that it is easier to grasp. 
Once you have understood expanded code correctly try to combining/shortening the commands; you will reach original code.

Java code.
Also shared at

public class SubsetSumProblem {

public static void main(String[] args) {
int set[] = {12, 34, 4, 3, 5, 2};
 int sum = 9;
 int n = set.length;
 if (isSubsetSum(set, n, sum) == true)
    System.out.println("Found a subset with given sum");
 System.out.println("No subset with given sum");

// Returns true if there is a subset of set[] with sun equal to given sum
public static boolean isSubsetSum(int set[], int n, int sum)
   // The value of subset[i][j] will be true if there is a subset of set[0..j-1]
   //  with sum equal to i
boolean subset[][] = new boolean[sum+1][n+1];
   // If sum is 0, then answer is true
   for (int i = 0; i <= n; i++)
     subset[0][i] = true;
   // If sum is not 0 and set is empty, then answer is false
   // This is not needed in Java as default value of boolean is false. 
//    for (int i = 1; i <= sum; i++)
//      subset[i][0] = false;

    // Fill the subset table in bottom up manner
    for (int i = 1; i <= sum; i++)
      for (int j = 1; j <= n; j++)
      if(subset[i][j-1] == true){
    // it is possible to generate sum "i" from smaller subset itself. 
    // So obviously it can be generated by bigger one. So no need to think more
    subset[i][j] = true;   
      }else if (i == set[j-1]) {
      subset[i][j] = true;
      }else if (i >= set[j-1]) {
          //  sum "i" is bigger than set[j-1]. Lets say  set[j-1] + x = i
        // So x = i - set[j-1]
        // Now we need to refer currently populated array to check if "x" can be achieved by first j-1 elements.
          int x = i - set[j-1];
          subset[i][j] = subset[x][j-1];
    return subset[sum][n];

No comments:

Post a Comment