4
\$\begingroup\$

I solved the problem to print all possible subsets of an array. I just want to know a better approach or anything different I could have done.

Question: Print all possible subsets of an array.

My approach: I know that there are \$2^N\$ (no. of elements in the set) subsets and each subset can be represented with the help of \$N\$-bit binary number. As a part of an assignment I have already made a decimal to binary and to reverse(prints no. in reverse digit by digit) a number program.So I combined the two to solve this question.

Input: {1, 2, 3}

Output: 3, 2, 32, 1, 31, 21, 321

My Code:

private static void subset(int[] arr) {
    int size = arr.length;
    int binaryLimit = (int) Math.pow(2, size) - 1;
    for (int i = 0; i <= binaryLimit; i++) {       //generate decimal no.
        //generate corresponding binary no & counter(how many bit binary no. is)
        int N = i;
        int counter = 0;
        int power = 0, binary = 0;
        while (N != 0) {
            int rem = N % 2;
            rem = rem * ((int) Math.pow(10, power));
            binary = binary + rem;
            N = N / 2;
            power++;
            counter++;
        }
        // loop to traverse array
        for (int j = arr.length - 1; j >= arr.length - counter; j--) {
            // if binary no is greater then one digit, compare each digit separately.
            if (counter > 1) {
                int k = binary;
                while (k != 0) {
                    int rem = k % 10;
                    if (rem == 1) {     //if binary digit == 1, print corresponding no. from array
                        System.out.print(arr[j]);
                    }
                    j--;
                    k = k / 10;
                }
                System.out.println();
            } else {
                if (binary == 1) {
                    System.out.println(arr[j]);
                    j--;
                }
            }
        }
    }
}
\$\endgroup\$
0

1 Answer 1

Reset to default
6
\$\begingroup\$

Simplify

This could be written a lot simpler. For each number until binaryLimit, you could iterate over the bits using bit shifting, and moving the current index in the array, printing values when the bit is set.

private static void printAllSubsets(int... arr) {
    int size = arr.length;
    int binaryLimit = (1 << size) - 1;

    for (int i = 1; i <= binaryLimit; i++) {
        int index = size - 1;
        int num = i;
        while (num > 0) {
            if ((num & 1) == 1) {
                System.out.print(arr[index]);
            }
            index--;
            num >>= 1;
        }
        System.out.println();
    }
}

Calculating powers of 2

Note that Math.pow takes and returns double. Converting between types is ugly, and what's worse, floating point math is fraught with problems in general. Fortunately, for calculating powers of 2, a clean and blazingly fast alternative is to use bit shifting, as demonstrated in the code above.

Naming

subset is a poor name for a void method that prints subsets of elements of an array.

Usability

As there is no punctuation between elements as they are printed, this method will not be very useful for larger arrays, or arrays where values have more than one digit.

Java conventions

Capitalized variable names are normally used for constants, never for local variables.

Method decomposition

Your implementation is very long, and could have been split to smaller pieces that are easier to read and test individually.

\$\endgroup\$
10
  • \$\begingroup\$ thanks for your valuable answer. The reason why I don't upvote is that you suggest premature optimization which confuses my a little since you emphase readability with you next two points... \$\endgroup\$ Commented Jan 24, 2017 at 22:14
  • \$\begingroup\$ Which part is premature optimization in your opinion? \$\endgroup\$ Commented Jan 24, 2017 at 22:16
  • \$\begingroup\$ Thanks for the help. I'll surely keep in mind all the pointers. I just want to know what do u mean by the last point \$\endgroup\$ Commented Jan 24, 2017 at 23:01
  • \$\begingroup\$ Does it mean dividing code further into smaller methods? \$\endgroup\$ Commented Jan 24, 2017 at 23:04
  • 1
    \$\begingroup\$ @TimothyTruckle Apparently readability is in the eye of the beholder. It hurts me so much to see Math.pow(2, n). Even more painful was the conversion to a base 10 value named binary, only to have the next loop convert "binary" back to base 2. \$\endgroup\$ Commented Jan 25, 2017 at 11:28

You must log in to answer this question.