Unable to generate sub-sets of an array

Question

I am trying to find the subsets of an array. In example if the array is [1,2] I am trying to print the following:

[1][2]
[1]
[2]
null

The code that I have written is as follows:

    import java.util.*;

      class PrintArray {
           public static void printme(int a[], int pos, int size) {
              if (pos >= size)
               return;
           else
            System.out.println(a[pos]);
        pos++;
        printme(a, pos, size);
    }

    public static void generate(int a[], ArrayList<Integer> list, int pos, int size) {

        if (pos > size) {
            for (int i = 0; i < list.size() - 1; i++) {
                System.out.print("[" + list.get(i) + "]");
            }
            System.out.println();
            return;
        }

        list.add(a[pos]);
        generate(a, list, pos + 1, size);
        list.remove(list.size() - 1);
        generate(a, list, pos + 1, size);

    }

    public static void main(String args[]) {
        int ar[] = { 1, 2, 3, 4, 5 };
        // printme(ar, 0, ar.length);
        ArrayList<Integer> list = new ArrayList<Integer>();
        generate(ar, list, 0, ar.length);

    }
}

However I am running into the following OOBE error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds 

That can be resolved by checking for pos>=size instead of pos>size but such a change does not generate all the sub-arrays.

A follow-up problem is that I am getting duplicate outputs as shown below:

[2][3][4]
[2][3]
[2][3]
[2]
[2][4]
[2]
[2]

Could someone please help me in overcoming these 2 issues?

Answer 1

You can look at your subsets array as a matrix. For {x, y} array:

• the matrix will have 2^n elements, where n is the number of elements in the array;
• it can be visualized in binary, 1 means print the element and 0 doesn't print anything:

public static void main (String[] args) throws Exception
    {
        int ar[] = {1, 2};
        int nrOfSubsets = (int) Math.pow (2, ar.length); 

        // prints the subset matrix
        for (int i = nrOfSubsets - 1; i >= 0; i--)
        {
            String output = "";
            int temp = i;

            // prints one matrix line
            for (int j = ar.length - 1; j >= 0; --j)
            {
                 // convert to binary, 1 means print the number
                 int rem = temp % 2;
                 temp = temp / 2;
                 if (rem == 1)
                 {
                     output = "[" + ar[j] + "]" + output;
                 }
             }
            if(output.isEmpty()) output = "null";
            System.out.println (output);
        }
    }