Interview Questions

Print all subsets (power set) of a given set
The input for this problem will be an array of numbers representing a set, which only contains unique numbers, and your goal is to print every possible set combination, otherwise known as the power set. For example:
input set = [1, 2, 3] power set = [[], [1], [2], [3], [1, 2], [2, 3], [1, 3] [1, 2, 3]]
The power set contains every possible combination of numbers. It also includes the empty set which contains no numbers from the original set.

Algorithm

There will be 2N possible combinations of a set of length N because every element can either be in the set or not, which gives us 2 possibilities, and we do this for N numbers, giving us 2 * 2 * 2 ... = 2N.
(1) Loop from 0 to 2N (2) For each number get the binary representation of the number, e.g. 3 = 011 (3) Determine from the binary representation whether or not to include a number from the set, e.g. 011 = [exclude, include, include]

Example

input set = [1, 2, 3] The numbers 0 to 2N in binary are:
0 = 000 1 = 001 2 = 010 3 = 011 4 = 100 5 = 101 6 = 110 7 = 111
Now for each binary number we determine what numbers from the input set, [1, 2, 3], to include in the current set that we will add to the power set.
000 = [exclude, exclude, exclude] = [] 001 = [exclude, exclude, include] = [3] 010 = [exclude, include, exclude] = [2] 011 = [exclude, include, include] = [2, 3] 100 = [include, exclude, exclude] = [1] 101 = [include, exclude, include] = [1, 3] 110 = [include, include, exclude] = [1, 2] 111 = [include, include, include] = [1, 2, 3]
All of the resulting sets make up the power set for [1, 2, 3].

Code

```function powerSet(arr) {

// the final power set
var powers = [];

// the total number of sets that the power set will contain
var total = Math.pow(2, arr.length);

// loop through each value from 0 to 2^n
for (var i = 0; i < total; i++) {

// our set that we add to the power set
var tempSet = [];

// convert the integer to binary
var num = i.toString(2);

// pad the binary number so 1 becomes 001 for example
while (num.length < arr.length) { num = '0' + num; }

// build the set that matches the 1's in the binary number
for (var b = 0; b < num.length; b++) {
if (num[b] === '1') { tempSet.push(arr[b]); }
}

// add this set to the final power set
powers.push(tempSet);

}

return powers;

}

powerSet([1, 2, 3]);
```
```import math

def powerSet(arr):

# the final power set
powers = []

# the total number of sets that the power set will contain
total = int(math.pow(2, len(arr)))

# loop through each value from 0 to 2^n
for i in range(0, total):

# our set that we add to the power set
tempSet = []

# convert the integer to binary
num = "{0:b}".format(i)

# pad the binary number so 1 becomes 001 for example
while len(num) < len(arr):
num = '0' + num

# build the set that matches the 1's in the binary number
for b in range(0, len(num)):
if num[b] == '1':
tempSet.append(arr[b])

# add this set to the final power set
powers.append(tempSet)

return powers

print powerSet([1, 2, 3])
```

Running time

This algorithm runs in O(2n) time, which is very slow, because there are 2n possible sets in a power set for an input set with n elements. The algorithm must perform this many steps to calculate all the sets. [1]

Sources

http://www.glassdoor.com/Interview/Write-a-program-the-generates-the-power-set-of-a-set-of-numbers-QTN_24552.htm http://www.careercup.com/question?id=5670502550994944
mrdaniel published this on 11/12/15 |
• +
• 3
• -
• So in order to solve this one efficiently, do you recommend to use anything else ? For example Dynamic Programming ?
• +
• 1
• -
• ```from itertools import combinations

newlist = [[]]
l = [1,2,3]
for i in range(1,len(l)+1):
c = combinations(l,i)
for i in p:
newlist.append(list(i))
print(newlist)
```
• +
• 1
• -
• Easier to understand in a functional setting, e.g. Haskell ``` nonEmptySubsequences :: [a] -> [[a]] nonEmptySubsequences [] = [] nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs) where f ys rss = ys : (x : ys) : rss ``` λ nonEmptySubsequences [1,2,3] [[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
• +
• 0
• -
• Java code which follows the algorithm amenably.
```import java.util.*;

public class Main {
public static void main(String[] args) throws Exception {
int[] array = new int[]{1, 2, 3};
ArrayList<ArrayList<Integer>> results = generatePowerSets(array);

ArrayList<Integer> set;
System.out.print("[");
for (int i = 0; i < results.size(); i++) {

set = results.get(i);

System.out.print("[");
for (int j = 0; j < set.size(); j++) {

System.out.printf("%d%s",
set.get(j),
j < set.size() - 1 ? "," : "");
}
System.out.printf("]%s", i < results.size() - 1 ? "," : "");
}
System.out.println("]");
}

public static ArrayList<ArrayList<Integer>> generatePowerSets(int[] array) {
ArrayList<ArrayList<Integer>> results = new ArrayList<ArrayList<Integer>>();
for (int i = 0; i < Math.pow(2, array.length); i++) {
}
return results;
}

public static ArrayList<Integer> powerSets(int[] array, int n) {

ArrayList<Integer> result = new ArrayList<Integer>();
ArrayList<Integer> bin = convertToBin(n, array.length);
for (int i = 0; i < bin.size(); i++) {
if (bin.get(i) == 1) {
}
}
return result;

}

public static ArrayList<Integer> convertToBin(int n, int pad) {
// convert n (decimal) to binary
ArrayList<Integer> results = new ArrayList<Integer>();
while (n > 0) {
n = n / 2;
}

for (int i = 0; i < pad - results.size() + 1; i++) {
}
}

return results;
}
}

```
• +
• 0
• -
• This is recursive version of it by Go. I guess it's much easier than the iterative way.
```var powerset func([]int, int, []int, *[][]int)
powerset = func(subset []int, breakPoint int, selectedSoFar []int, result *[][]int) {
if len(subset) == breakPoint {
newArr := make([]int, len(selectedSoFar))
copy(newArr, selectedSoFar)
*result = append(*result, newArr)
return
} else {
selectedSoFar = append(selectedSoFar, subset[breakPoint])
powerset(subset, breakPoint+1, selectedSoFar, result)
selectedSoFar = selectedSoFar[:len(selectedSoFar)-1]
powerset(subset, breakPoint+1, selectedSoFar, result)
}
}

resultSet := make([][]int, 0)
selectedSoFar := make([]int, 0)
powerset(arr, 0, selectedSoFar, &resultSet)
```
• +
• 0
• -
• ```from typing import Callable
import sys

tsbst: list = [None]

def subset(sett: list) -> list:
biN:Callable[str, str] = lambda el : ''.join(reversed([str((el>>i) & 1) for i in range(len(sett))]))
tpx:int = 2**len(sett)
for i in range(1,tpx):
# breakpoint()
# print(list(biN(i%tpx)))
yield [i for i,j in zip(sett, list(biN(i%tpx))) if int(bool(i)) is int(j)]

# subset((lambda x : [input() for n in range(int(input("[+] NUMBER OF MEMBER SET : ")))])([]))
for sbst in subset(sys.argv[1].split(",")):
tsbst.append(set(sbst))

smallestTopol: set = [None, tsbst[len(tsbst)-1]]
largestTopol: list = tsbst

print(f"n[+] THE LARGEST TOPOLOGY ISnnt {largestTopol}n")
print(f"[+] THE SMALLEST TOPOLOGY ISnnt {smallestTopol}n")

```
• +
• -2
• -
• This problem may be solved in polynomial time.