Interview Questions

  • View all algorithm tutorials
  • blank
  • 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])   
    
    Run Code
    Run Code

    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 | array, math, subset, combination, Google, Facebook
    Comments
  • +
  • 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++) {
                results.add(powerSets(array, 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) {
                    result.add(array[i]);
                }
            }
            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) {
                results.add(0, n % 2);
                n = n / 2;
            }
            
            // zero padding
            if (results.size() < pad) {
                for (int i = 0; i < pad - results.size() + 1; i++) {
                    results.add(0, 0);
                }
            }
            
            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.
    Log in to submit a comment.