Skip to content

Instantly share code, notes, and snippets.

@thmain
Last active Jun 14, 2020
Embed
What would you like to do?
public class SubSetSum {
public static boolean subSetDP(int[] A, int sum) {
boolean[][] solution = new boolean[A.length + 1][sum + 1];
// if sum is not zero and subset is 0, we can't make it
for(int i=1;i<=sum;i++){
solution[0][i]=false;
}
// if sum is 0 the we can make the empty subset to make sum 0
for(int i=0;i<=A.length;i++){
solution[i][0]=true;
}
//
for(int i=1;i<=A.length;i++){
for(int j=1;j<=sum;j++){
//first copy the data from the top
solution[i][j] = solution[i-1][j];
//If solution[i][j]==false check if can be made
if(solution[i][j]==false && j>=A[i-1])
solution[i][j] = solution[i][j] || solution[i-1][j-A[i-1]];
}
}
return solution[A.length][sum];
}
public static void main(String[] args) {
int[] A = { 3, 2, 7, 1};
System.out.println("\nFrom DP: " + subSetDP(A, 6) );
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment