Code Author

Java Code : Sum of Subsets -Dynamic Programming

As explained earlier in the the program of sum of subsets given for C++ here the same fundamental or say basic working of the dynamic programming is use.

You can also check the C++ version of this program here

C++ : Sum of Subsets Using Dynamic Programming.

Dynamic programming works on the certain criteria

which  are explained into the comments as a wholesum.If any futher queries is to be asked regarding the working of the program or about the program's Dynamic approach users can just give their comments which are welcomed.

//Java Program to find subsets of desired sum using DP approach...
/**
 * @author Code Author
 */
import java.util.*;
public class Sum_of_subset {
    static Scanner console = new Scanner(System.in);
    
     //getting the number of elelments  thus defining array size globally so it can be used to define arraysize
       final static int n=console.nextInt();
       static int sum;
       
       // declaring and initializing array of size n
       // set : consistes of the set of numbers
       // receive : consistes of the subset included into the array to form desired sum
       static int[] set = new int[n];
       static int[] receive = new int[n];
       

    //Function to calculate sum of subset
    //w=intial weight or sum
    //total = total of the arrays elements
    public static void SOS(int i,int w,int total)
    {
     if(Acceptable(i,w,total))
     {
         //checking whether the weights are now equal to sum of subset or not
         if(w==sum)
         {
            //printting the subsets 
             System.out.println("Subset : ");
         
            for(int p=0;p<=i;p++)
            {
              if(receive[p]==1)
                 System.out.print(set[p]+" ");
            }
             System.out.println();
             return;   
         }
        receive[i+1]=1; //get the value here
      
        //calling recursively again by adding w i.e weight to the set[i+1] 
         //and simultaneously reducing that much from the total value 
         //to main the equilibrium betwweeen the datas 
         SOS(i+1,w+set[i+1],total-set[i+1]);
      
         //similary continuing for the all the elements
         receive[i+1]=0;
         SOS(i+1,w,total-set[i+1]);
         
     }
      
     
    }
    
    //method to check whether the given element is acceptable 
    //or not to be included into the array set whose sum should 
    //be equal to the given sum of subset
    //if it is return true else return false as not possible
    public static boolean Acceptable(int i,int w,int total)
    {
      if((w+total>=sum)&&(w==sum||w+set[i+1]<=sum)) 
          return true;
      return false;
    }
    
    static void print(int[] set)
    {
        for(int a:set)
            System.out.print(a + " ");
    }

public static void main(String[] args) {
     int total=0;
     System.out.println("Number of Elements : "+n);

    // Adding contents to the array
     System.out.print("Enter the contents of the array in any order : ");                
     for(int i =0;i<set.length;i++)
     {
         set[i] = console.nextInt();
         total +=set[i];
     }
     //sorting the array if not in ascending order for proper application of dynamic programming
     Arrays.sort(set);  
      
     //displaying the sorted array
     System.out.println("\nYour array is : ");
     print(set);
     
     System.out.println("Total is : "+total);
     
     //getting the sum to be calculated
     System.out.println("Enter the sum to be calculated i.e Sum of Subset : ");
     sum = console.nextInt();
     
     //calling the Sum of subset method
     SOS(-1,0,total);
     
    }

}

10
Number of Elements : 10
Enter the contents of the array in any order : 19 1 3 12 5 6 10 15 18 9

Your array is : 1 3 5 6 9 10 12 15 18 19
Total is : 98
Enter the sum to be calculated i.e Sum of Subset : 20
Subset  : 1 3 6 10 
Subset  : 1 9 10 
Subset  : 1 19 
Subset  : 3 5 12 
Subset  : 5 6 9 
Subset  : 5 15