1. Introduction

The Subset Sum Problem is a classic computer science problem that falls under the category of NP-complete problems. Given a set of non-negative integers, and a target value sum, determine if there is a subset of the given set with sum equal to the given sum. Dynamic programming offers an efficient pseudo-polynomial time solution to this problem.

2. Program Steps

1. Define a function isSubsetSum that takes the set of numbers, its size, and the desired sum as parameters.

2. Initialize a 2D boolean array subset with dimensions (n + 1) x (sum + 1).

3. Populate this table in a bottom-up manner. Each entry subset[i][j] will be true if there is a subset of the set[0…i-1] with sum equal to j.

4. Return the value in the last cell of the table: subset[n][sum].

5. In the main method, input a sample set and a target sum, then call isSubsetSum.

3. Code Program

class SubsetSumProblem {

    public static boolean isSubsetSum(int set[], int n, int sum) {
        boolean subset[][] = new boolean[n + 1][sum + 1];

        for (int i = 0; i <= n; i++) {
            subset[i][0] = true;
        }

        for (int i = 1; i <= sum; i++) {
            subset[0][i] = false;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                if (j < set[i - 1]) {
                    subset[i][j] = subset[i - 1][j];
                } else {
                    subset[i][j] = subset[i - 1][j] || subset[i - 1][j - set[i - 1]];
                }
            }
        }

        return subset[n][sum];
    }

    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)) {
            System.out.println("Found a subset with given sum");
        } else {
            System.out.println("No subset with given sum");
        }
    }
}

Output:

Found a subset with given sum

4. Step By Step Explanation

1. The function isSubsetSum determines if there is a subset within the given set that adds up to the provided sum.

2. For subset[i][j], if j is less than the current set element set[i-1], the value is derived from the value above it (subset[i-1][j]). Otherwise, it's either the value above it or the value found by moving left by the value of the current set element.

3. If the sum can be achieved by any combination up to the i-th element, subset[i][sum] will be true.

4. The main function demonstrates this with a sample set. The subset {4, 5} within the provided set sums up to 9.