Subset Sum Problem Interview Bit

 public class Solution {

    public int solve(int[] arr, int sum) {

        

        //Base Condition

        int n=arr.length;

        boolean t[][]=new boolean[n+1][sum+1];

            int a=0;

            for(int i=0;i<n+1;i++){

                for(int j=0;j<sum+1;j++){

                    if(i==0){

                        t[i][j]=false;

                        

                       

                    }

                    if(j==0){

                        t[i][j]=true;

                        

                        

                    }

                }

            }

            

            

            for(int i=1;i<n+1;i++){

                for(int j=1;j<sum+1;j++){

                    if(arr[i-1]>j){

                        t[i][j]=t[i-1][j];

                    }

                    else{

                        t[i][j]=(t[i-1][j]) || (t[i-1][j-arr[i-1]]); 

                    }

                }

            }

          boolean a1=t[n][sum];

           if(a1==true){

               return 1; 

           }

           else{

               return 0;

           }

        

        

        

        

    }

    

}

  

TIME:O(N*SUM)

SPACE:O(N*SUM)