Mr_HO1A

Sub Set Problem

Oct 26th, 2018
41
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 0.93 KB | None | 0 0
  1.  
  2. package javaapplication2;
  3.  
  4. public class JavaApplication2 {
  5.     public static void main(String[] args) {
  6.         int arr[] = {1,2,3,4,5,6,7,8};
  7.         int sum = 10;
  8.         subSetSum(arr, arr.length, sum);
  9.     }
  10.     static boolean subSetSum(int arr[],int n, int sum){
  11.         boolean mat[][] = new boolean[n+1][sum+1];
  12.         for(int i = 1; i<=sum; i++)
  13.             mat[0][i] = false;
  14.         for(int i = 0; i<=n; i++)
  15.             mat[i][0] = true;
  16.         for(int i = 1; i<=n;i++){
  17.             for(int j = 0;j<=sum;j++){
  18.                 mat[i][j] = mat[i-1][j];
  19.                 if(j>=arr[i-1]){
  20.                     mat[i][j] = mat[i][j] || mat[i-1][j - arr[i-1]];
  21.                 }
  22.             }
  23.         }
  24.         for(int x = 0; x<=n;x++){
  25.             for(int y = 0;y<=sum;y++){
  26.                 System.out.print(mat[x][y]+" ");
  27.             }
  28.             System.out.println("");
  29.         }
  30.         return false;
  31.     }
  32. }
Add Comment
Please, Sign In to add comment