Subset Sums in Java

Question

Given an array of integers, print sums of all subsets in it. Output should be printed in increasing order of sums.

Input :

arr[] = {2, 3}

Output:

0 2 3 5

Input :

arr[] = {2, 4, 5}

Output :

0 2 4 5 6 7 9 11

Input:

The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. The first line of each test case is N, N is the size of array. The second line of each test case contains N space separated values of the array arr[].

Output:

Output for each test case should be space separated sums in increasing order.

Constraints:

1 ≤ T ≤ 100

1 ≤ N ≤ 10

0 ≤ A[i] ≤ 100

Input:

2

2

1 2

3

5 2 1

Output:

0 1 2 3

0 1 2 3 5 6 7 8

My approach:

import java.util.Scanner;
import java.util.Collections;
import java.lang.StringBuffer;
import java.lang.Math;
import java.util.List;
import java.util.ArrayList;

class SubsetSums {

    private static List<Integer> subSetSums (int[] arr) {
        int len = arr.length;
        List<Integer> sums = new ArrayList<>();
        sums.add(0);
        List<String> binaryNumbers = new ArrayList<>();
        int limit = (int)Math.pow(2,len);

        for (int i = 1; i < limit; i++) {
            String bin = getBinary(i,len);
            binaryNumbers.add(bin);
        }

       /*
        for (String str : binaryNumbers) {
            System.out.println(str);
        }
       */

        for (int i = 0; i < binaryNumbers.size() ; i++) {
            List<Integer> subSet = new ArrayList<>();
            String binary = binaryNumbers.get(i);
            for (int j = 0; j < binary.length(); j++) {
                if (binary.charAt(j) == '1') {
                    subSet.add(arr[j]);
                }
            }
            int sum = getSum(subSet);
            sums.add(sum);
            subSet.clear();
        }  

        Collections.sort(sums);
        return sums;
    }

    private static int getSum (List<Integer> subSet) {
        int sum = 0;
        for (Integer elem : subSet) {
            sum += elem;
        }
        return sum;
    }

    private static String getBinary (int num, int len) {

        String bin = "";

        if (num == 1) {
            String zeros = "";
            int numZeros = len - 1;

            while (numZeros != 0) {
                zeros += "0";
                numZeros--;
            }
            return zeros.concat("1");
        }
        else {
            while (num != 0) {
            int rem = num%2;
            bin += String.valueOf(rem);
            num = num/2;
        }

        bin = new StringBuffer(bin).reverse().toString();

        String zeros = "";
        int numZeros = len - bin.length() ;

        while (numZeros != 0) {
            zeros = zeros + "0";
            numZeros--;
        }

        return (zeros.concat(bin));

        }
    }

    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int numTests = sc.nextInt();

        while (numTests-- > 0) {
            int size = sc.nextInt();
            int[] arr = new int[size];

            for (int i = 0; i < size; i++) {
                arr[i] = sc.nextInt();
            }
            List<Integer> finalSums = subSetSums(arr);
            for (Integer elem : finalSums) {
                System.out.print(elem + " ");
            }
            System.out.println();
        }
       sc.close();
    }
}

I have the following questions with regards to the above code:

1. How can I further improve my approach?

2. Is there a better way to solve this question?

3. Are there any grave code violations that I have committed?

4. Can space and time complexity be further improved?

Reference

Answer 1

Current code review:

1. (int)Math.pow(2,len) could be replaced with 1 << len;
2. Traverse binary representation of number without any other manipulations using bitwise and bit shift operators;

So, code can look like:

for (int i = 1; i < limit; i++) {
    int sum = 0;
    int cur = i;
    for (int j = 0; j < len; j++) {
        // tests if least significant bit is set
        if ((cur & 1) == 1) {
            sum += arr[j];
        }
        // shift to test next bit on next loop iteration
        cur = cur >> 1;
    }
    // do something with sum
}

About time complexity improvement:

In your case, for every subset of numbers, we count its sum from 'scratch', but, imagine we have two subsets - one includes 1st,3rd and 5th numbers, and second only 1st and 3rd. Knowing sum of first subset, we can easily evaluate sum of second: just add 5th number to it. So, think about following idea: make recursion function void getSums(int ind, int prevSum), where prevSum is that already precounted sum of some subset, which contains elements with index < ind. We start with getSums(0, 0) and then we have 2 choices: add element on ind index or not.

Code can look like:

void getSums(int ind, int prevSum) {
    if(id == arr.length) {
        sums.add(prevSum);
        return;
    }
    int sumIncludingInd = prevSum + arr[ind];        
    getSums(ind + 1, sumIncludingInd, sums, arr);
    int sumNotIncludingInd = prevSum;     
    getSUms(ind + 1, sumNotIncludingInd, sums, arr);
}

Time complexity in your case will be O(n * 2ⁿ), since we have 2ⁿ subsets and, to get the sum, n summing operations should be done. In recursive approach, on each step you need to do only one summing operation(or zero), which is O(1). So, overall time complexity will be O(2ⁿ).

Answer 2

Your main calculation revolves around adding integers to an ArrayList just to add them all up. Putting them in a list is an unnecessary step, you could sum them directly.

In my opinion the whole String getBinary (int num, int len) function and its usage makes the code much more confusing than it needs to be, adding a relatively large amount of tricky bug-prone code. Rather than building binary strings in somewhat mysterious way, or any other way, you could test the bits of the current mask (an integer) directly. The idiomatic way to test whether bit j of a mask is set is (mask & (1 << j)) != 0, there are some variants.

Putting that together, there is a large reduction in code:

private static List<Integer> subSetSums (int[] arr) {
    List<Integer> sums = new ArrayList<>();
    int limit = 1 << arr.length;

    for (int mask = 0; mask < limit; mask++) {
        // sum up the values that correspond to bits
        // that are set in the mask
        int sum = 0;
        for (int j = 0; j < arr.length; j++) {
            if ((mask & (1 << j)) != 0)
                sum += arr[j];
        }
        sums.add(sum);
    }

    Collections.sort(sums);
    return sums;
}