SubsetSum.java

class SubsetSum
   {
	    public static void main (String[] args)
      {
         int[] arr = {1,3,9,2};
	       System.out.println(isSol(arr,arr.length,5);
	      }
	    
	
        // Recursive solution - NP complexity 
                           
    	 static boolean isSol(int[] arr,int n,int sum)
         {	     
	          if(sum==0) return true; // mil gaya
	     
	          if(n==0 && sum!=0) return false; //pohoch gaye, but nahi mila 
	     
      	     if(arr[n-1]>sum) return isSol(arr,n-1,sum); //number khud sum se bada hain
	     
	           return (isSol(arr,n-1,sum-arr[n-1]) || isSol(arr,n-1,sum));    // number ko include karo aur na karo - dono check karo har baar
	 }                                                                  // start kiya hamne end se
	 
                            
                            
        
 // Dynamic programming method
                            
            static boolean isSolUsingDP(int[] arr, int sum){
        int n = arr.length;
        boolean[][] a = new boolean[n+1][sum+1];

        for(int i=0;i<n+1;i++) a[i][0]=true;
        for(int i=1;i<sum+1;i++) a[0][i]=false;

        for(int i=1;i<n+1;i++){
            for(int j=1;j<sum+1;j++){
                a[i][j]=a[i-1][j];

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

                    if(a[i][j] || a[i-1][j-arr[i-1]]) a[i][j] = true;

                }

            }
        }
        return a[n][sum];
    }
}