# Find all subsets of a set (Power Set)

### Print power set of any given set OR Print all subsets of a set OR Find all subsets of a set OR Print all subset of an array.

Given a set of numbers, print all the possible subsets of it including empty set.

### What is Power Set?

In mathematics, the power set (or powerset) of any set S, written P(S), is the set of all subsets of S, including the empty set and S itself.

Let's understand it with help of example.
Case 1:
Input:    Set(S)              = [1,2]
Output: PowerSet P(S) = [[ ], [2], [1], [2, 1]]

Case 2:
Input:    Set(S)              = [a,b,c]
Output: PowerSet P(S) = [[ ], [a], [b], [c], [a,b], [a, c], [b, c], [a, b, c]]

### Solution

There can be many approach to solve this problem, here we will look at 2 simple approaches.
1. Using Tree representation approach.
2. Using Bit manipulation approach.

### Tree Representation Approach

In this approach, we will draw a Tree like shown below,

There are 2 possibilities for each item of a set, It will be either included in a subset or not included.
Based on this fact, Lets draw a Tree for given Set [a, b, c].

There are 2 possibilities of "a". It will be either included in a subset or not included.
Similarly, For each possibilities of "a", again there are 2 possibilities for "b".

"b" will be included for each possibilities of "a" or not included.
Similarly, For each possibilities of "b", again there are 2 possibilities for "c".
Again, For "c", there are 2 possibilities either it will be considered or will be ignored in a subset.

Stop as there are no more items in a set remaining. Our Tree is complete and will look as shown in image above.

Lets understand our example and draw a Tree for it.
Set [a, b, c].

"a" is included.
1. "b" will be included in a subset.
2. "c" will be included in a subset.        END- No more element in Set.
2. "c" will not be included in a subset.    END- No more element in Set.

1. "b" will not be included in a subset.
2. "c" will be included in a subset.        END- No more element in Set.
2. "c" will not be included in a subset.    END- No more element in Set.

"a" is not included.
1. "b" will be included in a subset.
2. "c" will be included in a subset.        END- No more element in Set.
2. "c" will not be included in a subset.    END- No more element in Set.

1. "b" will not be included in a subset.
2. "c" will be included in a subset.        END- No more element in Set.
2. "c" will not be included in a subset.    END- No more element in Set.

Now, read the Tree from Bottom to Root. Wherever there is Yes, include the item in a subset, ignore otherwise.

"a" is included.
1. "b" will be included in a subset.
2. "c" will be included in a subset.          END- No more element in Set. = [ c, b, a ]
2. "c" will not be included in a subset.    END- No more element in Set. = [ b, a ]

1. "b" will not be included in a subset.
2. "c" will be included in a subset.          END- No more element in Set. = [ c,  a ]
2. "c" will not be included in a subset.    END- No more element in Set. = [ a ]

"a" is not included.
1. "b" will be included in a subset.
2. "c" will be included in a subset.          END- No more element in Set. = [ c, b ]
2. "c" will not be included in a subset.    END- No more element in Set. = [ b ]

1. "b" will not be included in a subset.
2. "c" will be included in a subset.          END- No more element in Set. = [ c ]
2. "c" will not be included in a subset.    END- No more element in Set. = [  ]

Subset or PowerSet of [a, b, c] is [  [ c, b, a ],  [ b, a ],  [ c, a ],  [ a ],  [ c, b ],  [ b ],  [ c ], [ ]  ]

### Understanding Program

Algorithm we will use for printing subset of a set is,

Step 1. Collect empty subset ([ ]) first because empty subset will be subset of any set including null set.
Step 2. Now, For each item of a Set, Iterate subsets already found and

1. Include a item in each subset and
2. Not include a item in each subset.

### Java Program for printing Subsets of set using Tree representation approach.

```package javabypatel;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class FindAllSubsetOfSet {

public static void main(String[] args) {
System.out.println("\n"+createSubsetUsingTree("A"));
}

private static List<String> createSubsetUsingTree(String str){

List<String> result = new ArrayList<String>(); // take set if you want unique results.

//If str is not null, then process further otherwise return empty set.
if(str!=null && str.length()>0){

//Iterate each element of a set
for (int i = 0; i < str.length(); i++) {

//Working on str.charAt(i);
//Store the result of subset of str.charAt(i) in tempList.
List<String> tempList = new ArrayList<String>();

//Add str.charAt(i) in each item of result.
Iterator<String> iter = result.iterator();
while(iter.hasNext()){
String val = iter.next();

// If val is [], it means str.charAt(i) is not included, So include it in result.
if(val.equals("[]")){
}else{

//For each item, there will be 2 subset, one including it and one without including it.
//If val is not [], it means it already contain some subset without str.charAt(i), So just include it.
tempList.add("[" + val.substring(1,val.length()-1) + ", " + str.charAt(i) + "]");
}
}

//Add all subsets present in tempList to final result.
}
}

return result;
}

}

```
Using List instead of String (Leetcode 78. Subsets) Recursive:
```package javabypatel;

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<List<Integer>> subsets(int[] nums) {

if(nums == null) {
return null;
}

List<List<Integer>> result = new ArrayList<>();

subsetsHelper(nums, 0, new ArrayList<Integer>(), result);
return result;
}

void subsetsHelper(int[] nums, int index, List<Integer> tempResult, List<List<Integer>> res) {

if (index >= nums.length) {
return;
}

List<Integer> tempList = new ArrayList<>(tempResult);

subsetsHelper(nums, index+1, tempResult, res);
subsetsHelper(nums, index+1, tempList, res);
}
}
```
Using List instead of String (Leetcode 78. Subsets) Iterative:
```package javabypatel;

import java.util.ArrayList;
import java.util.List;

class Solution {
public List<List<Integer>> subsets(int[] nums) {

if(nums == null) {
return null;
}

List<List<Integer>> result = new ArrayList<>();

for (int i=0; i<nums.length; i++) {

List<List<Integer>> tempResult = new ArrayList<>();

for (int j=0; j<result.size(); j++) {
List<Integer> temp = result.get(j);

List<Integer> newTemp = new ArrayList<>(temp);
//Keep as is
}
result = tempResult;
}

return result;
}
}

```

### Recursive Approach

```package javabypatel;

static void printSubsequences(int arr[], int index, String str) {
if (index >= arr.length) {
System.out.println("[" + str + "]");
return;
}

printSubsequences1(arr, index + 1, str + arr[index]);
printSubsequences1(arr, index + 1, str);
}

```

### Another Recursive Approach

```package javabypatel;

static void printSubsequences(int arr[], int index, String str) {
if (index >= arr.length) {
System.out.println(str);
return;
}

System.out.println(str);
for (int i = index; i < arr.length; i++) {
String str2 = str + arr[i];
printSubsequences(arr, i + 1, str2);
}
}

```

### Bit Manipulation Approach

In this approach we will use Bits Manipulation for printing Subset of a set.

Before going ahead, first lets understand how to check any bit is set in a byte.

Binary representation of a number 1 = 0001, 2 = 0010, ...., 5 = 0101, ....

How to identify whether LSB, that is bit at position 0 is set in 5(0101)?
Solution:

Do a Logical AND of 1 and 5 that is (0001 & 0101).
If the result is greater than 0, then LSB, that is bit at position 0 is set in value 5.

How to identify whether bit at position 1 is set in 5(0101)?

Solution:
Do a Logical AND of 2 and 5 that is (0010 & 0101).
If the result is greater than 0, then bit at position 1 is set

So, to generalize it, if we want to check nth bit is set in a number,

Step 1.
We will first take binary representation of 1 (0001),
Step 2.  Move the LSB in binary
representation of 1 to nth position.
Eg: If we want to check whether bit at position 2 is set,  then move 1 two times on right side,

= 1 << 2
=  0001 << 2
=  0100
Step 3. Once the LSB of binary 1 is moved to nth position, which we want to check,
just do logical AND of binary representation of 1 with the number,
If the result is greater than 0, then the bit is set, not otherwise.

If we want to find subset of 3 characters [a, b, c], then how many total subset can be made out of it?
If you observe, the number of subsets equals to 2 to the power of the number of elements in the set.
Number of subsets that can be made from set of 3 characters [a, b, c] is 2^3 = 8 subsets.
Number of subsets that can be made from set of 4 characters [a, b, c, d] is 2^4 = 16 subsets.
So, If there are n characters [a, b, c.... n] in a set, then there will be 2^n total subsets.

How to find total number of subsets possible using bit manipulation?
By shifting the bit representation of the number 1 by n, we will get 2^n.
Thus, if we shift the bit string of 1 by the number of elements in the given set, we'll get the number of subsets for that set.

For example, if we have S = [a, b, c], length of set here is 3,
So, for finding total subsets, we have to shift binary 1, 3 times,
1 << 3 = (0001 << 3) = (1000) = 2^3 = 8 subsets of set S.

If we compare subset of [a, b, c] to binaries representation of numbers from 0 to 7, we can find a relation with the bit sets in each number to subsets of [a, b, c].

### Java Program for printing Subsets of set using Bit Manipulation approach.

```package javabypatel;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class FindAllSubsetOfSet {

public static void main(String[] args) {
List<Object> list = new ArrayList<Object>();

System.out.println(getSubsetUsingBitMap(list));
}

private static Set<Set<Object>> getSubsetUsingBitMap(List<Object> list){

Set<Set<Object>> result = new HashSet<Set<Object>>();

int numOfSubsets = 1 << list.size(); //OR Math.pow(2, list.size())

// For i from 0 to 7 in case of [a, b, c],
// we will pick 0(0,0,0) and check each bits to see any bit is set,
// If set then element at corresponding position in a given Set need to be included in a subset.
for(int i = 0; i < numOfSubsets; i++){

Set<Object> subset = new HashSet<Object>();

int mask = 1; // we will use this mask to check any bit is set in binary representation of value i.

for(int k = 0; k < list.size(); k++){

if((mask & i) != 0){ // If result is !=0 (or >0) then bit is set.
subset.add(list.get(k)); // include the corresponding element from a given set in a subset.
}

// check next bit in i.
}

// add all subsets in final result.
}
return result;
}

}
```