public class SubsetSumSolver {


	public static String  targetSum(int startPoint, int[] values, int target) {

		//nothing left to be considered
		if (startPoint==values.length) {
				return "";
		}

		//check possibility #1: using the "first"
		if (values[startPoint]==target) return Integer.toString(target);

		String withFirst = targetSum(
				startPoint+1, values, target-values[startPoint]);
		if (!withFirst.equals("")) {
			return values[startPoint]+", "+withFirst;
		}

		//if not, check possibility #2
		String withoutFirst = targetSum(
				startPoint+1, values, target);
		if (!withoutFirst.equals("")) {
			return withoutFirst;
		}

		//if you get here, neither possibility worked
		return "";
	}

	public static void main(String[] args) {
		int[] vals = {3, 34, -7, 4, 12, 5, 2, 23};
		
		int sum = 0;
		for (int i=0; i<vals.length; i++) {
			if (vals[i]>0) sum+=vals[i];
		}
		
		for (int i=0; i<=sum; i++) {
			System.out.println("("+i+"): " + targetSum(0,vals,i));
		}
	}
}



//Copyright Evan Golub 2016