Objective: Given a set of numbers, print all the posssible subsets of it including empty set.
Power Set: In mathematics, PowerSet of any given set S, PS(S) is set of all subsets of S including empty set.
Example:
S ={1,2,3}
PS(S): {{ᵩ}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Approach:
Solution to this problem is similar to – Print All Combinations of subset of size K from Given Array
- Create an binary array of the same size as the given array.
- Now for every integer we have two options, whether to select it or ignore it.
- Now if we select it, we will put 1 in the boolean array at the corresponding index or if we ignore it, put 0 at that index.
- Say you have a variable called x, which represents the current index at the given array.
- Make x = 0 ( ignoring xth index) and x = 1( selecting xth index) and make recursive
Code:
| public class AllCombinations { | |
| static int[] B = { 1, 2, 3 }; | |
| public void combinations(int[] A, int x) { | |
| if (x == A.length – 1) { | |
| A[x] = 0; // last digit, don't select it | |
| printArray(A); // print the set | |
| A[x] = 1; //// last digit, select it | |
| printArray(A); | |
| return; | |
| } | |
| A[x] = 0; //either you will not select this digit | |
| combinations(A, x + 1); | |
| A[x] = 1; //either you will select this digit | |
| combinations(A, x + 1); | |
| } | |
| public void printArray(int[] A) { | |
| boolean isNULL = true; | |
| System.out.print("{"); | |
| for (int i = 0; i < B.length; i++) { | |
| if (A[i] == 1) { | |
| System.out.print(B[i] + ""); | |
| isNULL = false; | |
| } | |
| } | |
| if (isNULL == false) { | |
| System.out.print("}"); | |
| System.out.print(" "); | |
| } | |
| if (isNULL) { | |
| System.out.print("Empty"); | |
| System.out.print("} "); | |
| } | |
| } | |
| public static void main(String[] args) { | |
| AllCombinations a = new AllCombinations(); | |
| int[] A = new int[B.length]; | |
| a.combinations(A, 0); | |
| } | |
| } |
Output:
{Empty} {3} {2} {23} {1} {13} {12} {123}