This Java program solves the subset sum problem using dynamic programming. The goal is to determine whether a subset of a given set of integers can sum up to a specific target value.
Java Program
public class SubsetSum {
// Function to determine if a subset with the given sum exists
public static boolean isSubsetSum(int[] set, int sum) {
int n = set.length;
// DP table where dp[i][j] will be true if there is a subset
// of set[0..i-1] with sum equal to j
boolean[][] dp = new boolean[n + 1][sum + 1];
// If sum is 0, the answer is true (empty subset)
for (int i = 0; i <= n; i++) {
dp[i][0] = true;
}
// If set is empty and sum is not 0, the answer is false
for (int j = 1; j <= sum; j++) {
dp[0][j] = false;
}
// Fill the dp table
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= sum; j++) { // If the current element is greater than the sum, exclude it if (set[i – 1] > j) {
dp[i][j] = dp[i – 1][j];
} else {
// Include the current element or exclude it
dp[i][j] = dp[i – 1][j] || dp[i – 1][j – set[i – 1]];
}
}
}
// The result is stored in dp[n][sum]
return dp[n][sum];
}
public static void main(String[] args) {
int[] set = {3, 34, 4, 12, 5, 2};
int sum = 9;
// Determine if a subset with the given sum exists
boolean result = isSubsetSum(set, sum);
if (result) {
System.out.println(“A subset with the given sum exists.”);
} else {
System.out.println(“No subset with the given sum exists.”);
}
}
}
Explanation of the Program Structure
This program solves the subset sum problem using dynamic programming. The subset sum problem asks whether a subset of a given set of integers can sum up to a specific target value.
- isSubsetSum function: This function implements the dynamic programming solution for the subset sum problem. It takes two inputs: an array
set[]of integers and a target sumsum. The function returnstrueif there exists a subset whose sum equals the target, andfalseotherwise. - Dynamic Programming Table (dp): The DP table
dp[i][j]is a 2D boolean array wheredp[i][j]istrueif a subset of the firstielements ofsethas a sum equal toj. The table is filled in a bottom-up manner based on whether we include or exclude the current element. - Main logic: The program iterates through the set and builds the DP table. For each element, we check if we can either include the element in the subset (if it doesn’t exceed the current sum) or exclude it. If the element is larger than the current sum, we exclude it. The final answer is found in
dp[n][sum], wherenis the number of elements in the set. - Base cases:
- If the target sum is 0, the answer is always
truebecause the empty subset can sum to 0. - If the set is empty and the target sum is non-zero, the answer is
falsebecause no subset can form a non-zero sum.
- If the target sum is 0, the answer is always
- main function: This function initializes a sample set of integers and a target sum, then calls the
isSubsetSumfunction to determine if a subset with the given sum exists. It prints the result to the console.
Step-by-Step Process:
- We initialize a dynamic programming table
dpof size(n+1) x (sum+1), wherenis the number of elements in the set, andsumis the target value. - We iterate through each element of the set. For each element, we update the DP table based on whether we can include or exclude the element from a subset that sums to the target value.
- The base case handles the situations when the sum is 0 or when the set is empty.
- The final result is stored in
dp[n][sum], which indicates whether a subset with the given sum exists or not.
Example:
Consider the following set of integers:
set = {3, 34, 4, 12, 5, 2}
target sum = 9
In this case, there exists a subset {4, 5} that sums to 9. The program will output:
A subset with the given sum exists.
Conclusion:
This Java program efficiently solves the subset sum problem using dynamic programming. The time complexity of this solution is O(n * sum), where n is the number of elements in the set, and sum is the target value. This approach ensures that we explore all possible subsets and determine whether a subset with the given sum exists.
