|
| 1 | +package DynamicProgramming; |
| 2 | + |
| 3 | +public class SubsetSum { |
| 4 | + |
| 5 | + /* |
| 6 | + This algorithm will determine if a set of integers contains |
| 7 | + a subset that sum to a given integer. The algorithm will |
| 8 | + return true if such a subset exists and false otherwise. |
| 9 | + This is a dynamic programming implementation. |
| 10 | + */ |
| 11 | + |
| 12 | + private static boolean subsetSum(int arr[], int n, int sum){ |
| 13 | + boolean isSum[][] = new boolean[n + 2][sum + 1]; |
| 14 | + |
| 15 | + isSum[n + 1][0] = true; |
| 16 | + for (int i = 1; i <= sum; i++) { |
| 17 | + isSum[n + 1][i] = false; |
| 18 | + } |
| 19 | + |
| 20 | + for (int i = n; i > 0; i--) { |
| 21 | + isSum[i][0] = true; |
| 22 | + for (int j = 1; j <= arr[i - 1] - 1; j++) { |
| 23 | + if (j <= sum) { |
| 24 | + isSum[i][j] = isSum[i + 1][j]; |
| 25 | + } |
| 26 | + } |
| 27 | + for (int j = arr[i - 1]; j <= sum; j++) { |
| 28 | + isSum[i][j] = (isSum[i + 1][j] || isSum[i + 1][j - arr[i - 1]]); |
| 29 | + } |
| 30 | + } |
| 31 | + |
| 32 | + return isSum[1][sum]; |
| 33 | + } |
| 34 | + |
| 35 | + /* |
| 36 | + This is a driver method to run the algorithm with four |
| 37 | + test values: the first two should evaluate true, and the |
| 38 | + last two should evaluate false. |
| 39 | + */ |
| 40 | + public static void main(String args[]) { |
| 41 | + int arr[] = new int[]{50, 4, 10, 15, 34}; |
| 42 | + int n = arr.length; |
| 43 | + // 4 + 10 + 15 + 34 = 64 |
| 44 | + int sum1 = 64; |
| 45 | + // 50 + 15 + 34 = 99 |
| 46 | + int sum2 = 99; |
| 47 | + // No subset of the given array will give a sum |
| 48 | + // of 5 or 66 |
| 49 | + int sum3 = 5; |
| 50 | + int sum4 = 66; |
| 51 | + |
| 52 | + System.out.println(subsetSum(arr, n, sum1)); |
| 53 | + System.out.println(subsetSum(arr, n, sum2)); |
| 54 | + System.out.println(subsetSum(arr, n, sum3)); |
| 55 | + System.out.println(subsetSum(arr, n, sum4)); |
| 56 | + } |
| 57 | +} |