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:
## Algorithm

There will be 2^{N} 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 ... = 2^{N}.
## Example

input set = [1, 2, 3]
The numbers 0 to 2^{N} in binary are:
## Code

## Running time

This algorithm runs in O(2^{n}) time, which is very slow, because there are 2^{n} 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

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.
(1) Loop from 0 to 2^{N}
(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]

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

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 ?

ntt2k

commented on 12/20/16

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

rayqiu

commented on 11/12/18

0

This problem may be solved in polynomial time.

UsmanArif

commented on 11/09/18

Log in to submit a comment.