Subset Sum Problem - Java Solution

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.