SubsetSum.java

packagecom.thealgorithms.dynamicprogramming;

publicclassSubsetSum {

/**
 * Driver Code
 */
publicstaticvoidmain(String[] args) {
int[] arr = newint[] {50, 4, 10, 15, 34};
assertsubsetSum(arr, 64);
/* 4 + 10 + 15 + 34 = 64 */
assertsubsetSum(arr, 99);
/* 50 + 15 + 34 = 99 */
assert !subsetSum(arr, 5);
assert !subsetSum(arr, 66);
 }

/**
 * Test if a set of integers contains a subset that sum to a given integer.
 *
 * @param arr the array contains integers.
 * @param sum target sum of subset.
 * @return {@code true} if subset exists, otherwise {@code false}.
 */
publicstaticbooleansubsetSum(int[] arr, intsum) {
intn = arr.length;
boolean[][] isSum = newboolean[n + 2][sum + 1];

isSum[n + 1][0] = true;
for (inti = 1; i <= sum; i++) {
isSum[n + 1][i] = false;
 }

for (inti = n; i > 0; i--) {
isSum[i][0] = true;
for (intj = 1; j <= arr[i - 1] - 1; j++) {
if (j <= sum) {
isSum[i][j] = isSum[i + 1][j];
 }
 }
for (intj = arr[i - 1]; j <= sum; j++) {
isSum[i][j] = (isSum[i + 1][j] || isSum[i + 1][j - arr[i - 1]]);
 }
 }

returnisSum[1][sum];
 }
}