3
\$\begingroup\$

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[0].put(sum, arr[0] == 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[0] == sum) 
            { 
                str += arr[0];
                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.
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.