SubsetSum.java

/*
    Problem: Given an array of integers and sum S,
             find whether the subset exists to create sum S or not.
 */
import java.util.ArrayList;
import java.util.List;

public class SubsetSum {
    // complexity: time O(n*m), space O(n*m), n: number of integers, m: sum
    static boolean canMakeSubset(int[] ary, int sum) {
        boolean[][] memo = new boolean[ary.length + 1][sum + 1];
        // initialize
        // if sum is not zero and subset is 0, we can't make it
        for(int i = 1; i <= sum; i++){
            memo[0][i]=false;
        }
        // if sum is 0 the we can make the empty subset to make sum 0
        for(int i = 0; i <= ary.length; i++){
            memo[i][0]=true;
        }

        // fill the rest
        for(int i = 1; i <= ary.length; i++){
            for(int j = 1; j <= sum; j++){
                // copy from previous row
                memo[i][j] = memo[i - 1][j];
                if(memo[i][j] == false && j >= ary[i - 1])
                    memo[i][j] = memo[i][j] || memo[i - 1][j - ary[i - 1]];
            }
        }
        if (memo[ary.length][sum]) {
            printResult(ary, memo);
        }
        return memo[ary.length][sum];
    }

    static void printResult(int[] ary, boolean[][] memo) {
        List<Integer> result = new ArrayList();
        int row = memo.length - 1;
        int col = memo[0].length - 1;
        while (row > 0 && col > 0) {
            if (memo[row][col]) {
                if (!memo[row - 1][col]) {
                    result.add(ary[row - 1]);
                    col -= ary[row - 1];
                }

            }
            row--;
        }
        System.out.println(result);
    }

    public static void main(String[] args) {
        int[] A = { 3, 2, 7, 1};
        System.out.println(canMakeSubset(A, 6));
        int[] B = { 3, 2, 7, 4};
        System.out.println(canMakeSubset(B, 6));
        int[] C = { 3, 1, 7, 4};
        System.out.println(canMakeSubset(C, 6));
    }

}

/*
References:
http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/
http://www.geeksforgeeks.org/dynamic-programming-subset-sum-problem/
*/