fork download
copy 
  1. //Java implementation for subset sum
  2. // problem using tabulation
  3. import java.util.*;
  4.  
  5. class GfG {
  6.  
  7.     // Function to check if there is a subset of arr[]
  8.     // with sum equal to the given sum using tabulation
  9.        static boolean isSubsetSum(int[] arr, int sum) {
  10.         int n = arr.length;
  11.  
  12.         // Create a 2D array for storing results of
  13.         // subproblems
  14.         boolean[][] dp = new boolean[n + 1][sum + 1];
  15.  
  16.         // If sum is 0, then answer is true
  17.           // (empty subset)
  18.         for (int i = 0; i <= n; i++) {
  19.             dp[i][0] = true;
  20.         }
  21.  
  22.         // Fill the dp table in bottom-up manner
  23.         for (int i = 1; i <= n; i++) {
  24.             for (int j = 1; j <= sum; j++) {
  25.                 if (j < arr[i - 1]) {
  26.  
  27.                     // Exclude the current element
  28.                     dp[i][j] = dp[i - 1][j];
  29.                 }
  30.                 else {
  31.  
  32.                     // Include or exclude
  33.                     dp[i][j] = dp[i - 1][j]
  34.                                || dp[i - 1][j - arr[i - 1]];
  35.                 }
  36.             }
  37.         }
  38.  
  39.         return dp[n][sum];
  40.     }
  41.  
  42.     public static void main(String[] args) {
  43.  
  44.         int[] arr = { 3, 34, 4, 12, 5, 2 };
  45.         int sum = 9;
  46.  
  47.         if (isSubsetSum(arr, sum)) {
  48.             System.out.println("True");
  49.         }
  50.         else {
  51.             System.out.println("False");
  52.         }
  53.     }
  54. }
Success #stdin #stdout 0.11s 54460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
True
https://ideone.com/4HH6ap
language:
Java (HotSpot 12)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!