HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Print all possible subsets of an array

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
allarraysubsetspossibleprint

Problem

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 = 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--;
                }
            }
        }
    }
}

Solution

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  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.

Code Snippets

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();
    }
}

Context

StackExchange Code Review Q#153514, answer score: 6

Revisions (0)

No revisions yet.