# Convert top-down subset sum to bottom-up

I have written the code for calculating subset-sum and also printing the first encountered non-empty subset from the left that sums up to the given sum.

My code in Java is as follows:

import java.util.HashMap;
import java.util.Map;

public class SubsetSum {

public static void main(String[] args) {

int set[] = {-2, -3, 5, 7};

int sum = 10;

findSubsetSum(set, sum, set.length - 1);
}

public static void findSubsetSum(int arr[], int sum, int limit) {

Map<Integer, Boolean> memo[] =
new Map[limit + 1];

for(int i = 0; i < memo.length ; i++) {
memo[i] = new HashMap<Integer, Boolean>();
}

int A = 0, B = 0;

for(int i = 0 ; i <= limit; i++) {
if(arr[i] < 0) A+=arr[i];
else if(arr[i] >= 0) B+=arr[i];
}
//This is there just in case the set size is 1.
memo.put(sum, arr == sum);

for(int i = 1; i <= limit && limit < arr.length; i++) {
Q(arr, sum, i, A, B, memo);
}

boolean prev = Boolean.parseBoolean(memo[limit].get(sum)+"");

String str = "{";

Integer found =null;
int s = sum;

for(int i = limit - 1; i >= 0 && (found==null || found != sum); i--) {

if(i == 0 && (found == null ? 0 : found) + arr == sum)
{
str += arr;
break;
}

boolean b = Boolean.parseBoolean(memo[i].get(s)+"");

if(!b && prev) {
s-=arr[i + 1];
found = (found == null ? 0 : found) + arr[i + 1];
str+=arr[i + 1] + " ";
i++;
}
}

str+="}";

System.out.println(str);
}

private static boolean Q(int arr[], int sum, int index,
int A, int B, Map<Integer, Boolean> memo[]) {

if(index < 0) return false;

if(sum < A || sum > B) return false;

Boolean c = memo[index].get(sum);

if(c != null) return c;

Boolean res = Q(arr, sum, index - 1, A, B, memo)
|| arr[index] == sum
|| Q(arr, sum - arr[index], index - 1, A, B, memo);

memo[index].put(sum, res);

return res;
}

}


Some of the improvements I need help with are the following:

1. Convert the DP approach from top-down to a bottom-up approach. Is it really necessary for me to keep the whole memo[] array in memory ? Or can I optimize it somehow ?
2. I am really interested in how I can optimize my subset printing code. It begins from the 22nd line of the function findSubsetSum. I really am sure there is a more elegant way to do it, but I just can't think of it.
3. Any other code/logic improvements in general.