Subset sum problem.

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

Reference 

http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/

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

http://ideone.com/uUxNgb

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");

 else

 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];

}

 

}