WikiGalaxy
Subset Sum Problem Using Dynamic Programming
Understanding the Subset Sum Problem:
The subset sum problem is a classic decision problem in computer science. Given a set of integers, the task is to determine if there is a non-empty subset whose sum is equal to a given integer. This problem is NP-complete, but can be efficiently solved using dynamic programming.
import java.util.Arrays;
class SubsetSum {
static boolean isSubsetSum(int set[], int n, int sum) {
boolean subset[][] = new boolean[sum + 1][n + 1];
for (int i = 0; i <= n; i++)
subset[0][i] = true;
for (int i = 1; i <= sum; i++)
subset[i][0] = false;
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
subset[i][j] = subset[i][j - 1];
if (i >= set[j - 1])
subset[i][j] = subset[i][j] || subset[i - set[j - 1]][j - 1];
}
}
return subset[sum][n];
}
public static void main(String args[]) {
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset with given sum");
else
System.out.println("No subset with given sum");
}
}
Dynamic Programming Approach:
The dynamic programming solution to the subset sum problem involves creating a 2D array where each entry subset[i][j] indicates whether there is a subset of the first j elements that has a sum equal to i. The solution builds up from smaller problems to solve the original problem efficiently.
Console Output:
Found a subset with given sum
Subset Sum with Negative Numbers
Handling Negative Numbers:
The subset sum problem can also include negative numbers. This requires adjusting the dynamic programming table to handle negative indices or shifting the entire set to positive numbers.
import java.util.Arrays;
class SubsetSumNegative {
static boolean isSubsetSum(int set[], int n, int sum) {
int total = Arrays.stream(set).sum();
if (sum > total || sum < -total) return false;
boolean subset[][] = new boolean[2 * total + 1][n + 1];
int offset = total;
for (int i = 0; i <= n; i++)
subset[offset][i] = true;
for (int i = -total; i <= total; i++) {
for (int j = 1; j <= n; j++) {
subset[i + offset][j] = subset[i + offset][j - 1];
if (i - set[j - 1] + offset >= 0 && i - set[j - 1] + offset <= 2 * total)
subset[i + offset][j] = subset[i + offset][j] || subset[i - set[j - 1] + offset][j - 1];
}
}
return subset[sum + offset][n];
}
public static void main(String args[]) {
int set[] = {-3, 34, 4, -12, 5, 2};
int sum = 9;
int n = set.length;
if (isSubsetSum(set, n, sum) == true)
System.out.println("Found a subset with given sum");
else
System.out.println("No subset with given sum");
}
}
Adjusting for Negative Indices:
By shifting the problem space, we can handle negative numbers without changing the core logic of the dynamic programming approach. This ensures that all indices remain positive and accessible.
Console Output:
Found a subset with given sum
Subset Sum with Exact Match
Finding an Exact Subset:
Sometimes, the requirement is not just to check if a subset exists but to find the exact subset that sums up to the target. This can be done by backtracking through the DP table.
import java.util.ArrayList;
import java.util.List;
class SubsetSumExact {
static boolean isSubsetSum(int set[], int n, int sum, List subset) {
boolean dp[][] = new boolean[sum + 1][n + 1];
for (int i = 0; i <= n; i++)
dp[0][i] = true;
for (int i = 1; i <= sum; i++)
dp[i][0] = false;
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1];
if (i >= set[j - 1])
dp[i][j] = dp[i][j] || dp[i - set[j - 1]][j - 1];
}
}
if (dp[sum][n]) {
int i = sum, j = n;
while (i > 0 && j > 0) {
if (!dp[i][j - 1]) {
subset.add(set[j - 1]);
i -= set[j - 1];
}
j--;
}
}
return dp[sum][n];
}
public static void main(String args[]) {
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.length;
List subset = new ArrayList<>();
if (isSubsetSum(set, n, sum, subset)) {
System.out.println("Found a subset with given sum: " + subset);
} else {
System.out.println("No subset with given sum");
}
}
}
Backtracking to Find Subset:
By tracing back through the dynamic programming table, we can reconstruct the subset that forms the desired sum. This allows us to not only verify the presence of a subset but also to retrieve it.
Console Output:
Found a subset with given sum: [4, 5]
Subset Sum for Large Sets
Optimizing for Large Input Sets:
For large input sets, optimizing the space complexity becomes crucial. Using a 1D array instead of a 2D array can significantly reduce memory usage while solving the subset sum problem.
class SubsetSumLarge {
static boolean isSubsetSum(int set[], int n, int sum) {
boolean dp[] = new boolean[sum + 1];
dp[0] = true;
for (int num : set) {
for (int i = sum; i >= num; i--) {
dp[i] = dp[i] || dp[i - num];
}
}
return dp[sum];
}
public static void main(String args[]) {
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 30;
int n = set.length;
if (isSubsetSum(set, n, sum))
System.out.println("Found a subset with given sum");
else
System.out.println("No subset with given sum");
}
}
Space Optimization:
By iterating backward through the sum array, we ensure that each number is only used once per iteration, effectively reducing the space complexity from O(sum*n) to O(sum).
Console Output:
No subset with given sum
Subset Sum with Multiple Solutions
Finding All Possible Subsets:
In some cases, it might be necessary to find all subsets that sum up to a given value. This can be achieved by modifying the dynamic programming approach to store all possible solutions.
import java.util.ArrayList;
import java.util.List;
class SubsetSumMultiple {
static void findSubsets(int set[], int n, int sum, List current, List> allSubsets, boolean dp[][]) {
if (sum == 0) {
allSubsets.add(new ArrayList<>(current));
return;
}
if (n == 0) return;
if (dp[sum][n - 1]) {
findSubsets(set, n - 1, sum, current, allSubsets, dp);
}
if (sum >= set[n - 1] && dp[sum - set[n - 1]][n - 1]) {
current.add(set[n - 1]);
findSubsets(set, n - 1, sum - set[n - 1], current, allSubsets, dp);
current.remove(current.size() - 1);
}
}
static List> subsetSum(int set[], int n, int sum) {
boolean dp[][] = new boolean[sum + 1][n + 1];
for (int i = 0; i <= n; i++)
dp[0][i] = true;
for (int i = 1; i <= sum; i++)
dp[i][0] = false;
for (int i = 1; i <= sum; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i][j - 1];
if (i >= set[j - 1])
dp[i][j] = dp[i][j] || dp[i - set[j - 1]][j - 1];
}
}
List> allSubsets = new ArrayList<>();
findSubsets(set, n, sum, new ArrayList<>(), allSubsets, dp);
return allSubsets;
}
public static void main(String args[]) {
int set[] = {3, 34, 4, 12, 5, 2};
int sum = 9;
int n = set.length;
List> allSubsets = subsetSum(set, n, sum);
System.out.println("Subsets with given sum: " + allSubsets);
}
}
Generating Multiple Solutions:
By recursively exploring all paths in the DP table that lead to the target sum, we can generate all possible subsets that satisfy the condition. This approach provides a comprehensive solution set.
Console Output:
Subsets with given sum: [[4, 5], [3, 4, 2]]
