find a solution to subset sum using dynamic programming

Question

What I want to do

I want to find a subset of an array that sums to a target T. I also want to use to a dynamic programming approach (and a bottom-up solution at that) to do this.

What I currently have

Currently I only found a way to see if amongst all subsets of size N, whether or not there is at least one subset that has the desired sum. See code below.

public boolean solve(int[] numbers, int target) {

    //Safeguard against invalid parameters
    if ((target < 0) || (sum(numbers) < target)){
        return false;
    }

    boolean [][] table = new boolean [target + 1] [numbers.length + 1]  ;

    for (int i = 0; i <= numbers.length; ++i) {
        table[0][i] = true;
    }


    /* Base cases have been covered. 
     * Now look set subsets [1..n][target] to be true or false.
     * n represents the number of elements from the start that have a subset 
     * that sums to target
     */
    for (int i = 1; i <= target; ++i){
        for (int j = 1; j <= numbers.length; ++j){
            /* Mark index j as one of the numbers in the array
             *  which is part of the solution with the given subtarget */
            table [i][j] = table[i][j-1];
            if (i >= numbers[j-1])
                table[i][j] = table[i][j] || table[i - numbers[j-1]] [j-1];
        }
    }

    return table[target][numbers.length];
}

Where I am stuck

Right now, I know if there is a solution, but I can't think of a way to actually output a solution.

I am not looking for anyone to provide me specific code, but pseudocode is welcome as are hints to how a solution may be saved.

Answer 1

The algorithm you provided can stay the same, you don't need to store anything else besides the DP-table table[][]. You just need an additional post-processing phase in which you step "backwards" through table[][] to get the solution set.

Just to recall:

You've computed the table table[i][j], which stores for every value 0<=i<=t(:=target) and every 0<=j<=n(:=numbers.length) whether there is a subset of numbers in numbers[0..j-1] that sum to i.

Consider the subset S corresponding to table[i][j] (, which is true). Note that:

• The subset S contains the number numbers[j] only if table[ i-numbers[j] ][j-1] is true.

(Proof: recursively take the solution subset S' for table[ i-numbers[j] ][j-1], and add numbers[j])

On the other hand, this subset S does not contain the number numbers[j] only if table[ i-numbers[j] ][j-1] is false.

(Proof: assume S contains numbers[j], trow numbers[j] out of S, this implies table[ i-numbers[j] ][j-1], contradiction) So to get the subset, simply use the above property to check whether numbers[n-1] is in the subset summing to t.

• If so, recursively compute whether numbers[n-2] is in the subset summing to t-numbers[n-1],
• else recursively compute whether numbers[n-2], is in the subset summing to t