# 1. Introduction

This blog post addresses the Subset Sum problem, a classic problem in computer science and combinatorial optimization. The challenge is to determine if there is a subset of a given set of non-negative integers that sums up to a specific value.

## Problem

Given a set of non-negative integers and a value sum, determine if there is a subset of the given set with a sum equal to the given sum.

# 2. Solution Steps

1. Use dynamic programming to create a boolean 2D array dp where dp[i][j] is true if there is a subset of the first i numbers that add up to j.

2. Initialize the first column of dp as true, since a sum of 0 can always be achieved with no elements.

3. Fill the rest of dp table using the given set of numbers.

4. The answer will be the value in dp[n][sum], where n is the number of elements in the set.

# 3. Code Program

``````public class Solution {

// Main method for testing
public static void main(String[] args) {
int[] values1 = {3, 34, 4, 12, 5, 2};
System.out.println("Subset with sum 9 exists: " + isSubsetSum(values1, 9));

int[] values2 = {3, 34, 4, 12, 5, 2};
System.out.println("Subset with sum 30 exists: " + isSubsetSum(values2, 30));
}

// Method to check if a subset with the given sum exists
public static boolean isSubsetSum(int[] values, int sum) {
int n = values.length;
boolean[][] dp = new boolean[n + 1][sum + 1];

// Initialize the first column as true
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}

// Fill the subset table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) {
if (values[i - 1] <= j) {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - values[i - 1]];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][sum];
}
}
``````

### Output:

```Subset with sum 9 exists: True
Subset with sum 30 exists: False
```

### Explanation:

For the first input set {3, 34, 4, 12, 5, 2} and sum = 9, the isSubsetSum method returns True because a subset {4, 5} sums up to 9.

For the second input set and sum = 30, it returns False as there is no subset with the sum 30.

The method uses dynamic programming to efficiently find if a subset-sum exists that matches the target.

# My Top and Bestseller Udemy Courses

Check out all my Udemy courses and updates:
Udemy Courses - Ramesh Fadatare