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

**Reference**

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

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

}

}

## No comments:

## Post a Comment