# Recursive implementation of power set in Python

I was doing a recursion problem called power set, and would like to get code review. Here's the problem.

# Power Set:   Given a set S, return the powerset P(S), which is
#           a set of all subsets of S.
#
# Input:    A String
# Output:   An Array of String representing the power set of the input
#
# Example:  S = "abc", P(S) = ['', 'a', 'b', 'c', 'ab', 'ac', 'bc', 'abc']
#
# Note:     The input string will not contain duplicate characters
#           The letters in the subset string must be in the same order
#           as the original input.


I also draw out an example of recursive tree in the following example:

# input: "abc"
# output: ["", "a", "b", "c", "ab", "ac", bc", "abc"]
2 * 2 * 2  = 8  total
_  _   _
#  index
#  a  b  c
#                                          "",i=0
#                      /                                           \
#                       "a",i=1                                   "", i= 1
#                  /           \                           /                  \
#              "ab",i=2          "a",i=2                 "b", i=2             "" i=2
#              /    \            /      \                /     \              /       \
#        "abc", i=3 "ab", i=3  "ac",i=3  "a", i=3   "bc", i=3  "b", i=3     "c", i=3  "", i = 3
#         ret        ret         ret        ret        ret         ret      ret          ret

# result = ["abc", "ab", "ac", "a", "bc", "b", "c", ""]


python solution

def powerset(input):
results = []

def recurse(build, depth):
if (depth == len(input)):
results.append(build)
return

recurse(build, depth + 1)
recurse(build + input[depth], depth + 1)

recurse('', 0)
return results


The solution passes all of the tests.

# ###########################################################
# ##############  DO NOT TOUCH TEST BELOW!!!  ###############
# ###########################################################

from cStringIO import StringIO
import sys

# custom expect function to handle tests
# List count : keeps track out how many tests pass and how many total
#   in the form of a two item array i.e., [0, 0]
# String name : describes the test
# Function test : performs a set of operations and returns a boolean
#   indicating if test passed
def expect(count, name, test):
if (count is None or not isinstance(count, list) or len(count) != 2):
count = [0, 0]
else:
count[1] += 1

result = 'false'
errMsg = None
try:
if test():
result = ' true'
count[0] += 1
except Exception, err:
errMsg = str(err)

print('  ' + (str(count[1]) + ')   ') + result + ' : ' + name)
if errMsg is not None:
print('       ' + errMsg + '\n')

# code for checking if lists contain the same elements
def lists_matching(lst1, lst2):
if len(lst1) != len(lst2):
return False

cache = {}
for i in xrange(0, len(lst1)):
if lst1[i] in cache:
cache[lst1[i]] += 1
else:
cache[lst1[i]] = 1
for j in xrange(0, len(lst2)):
if lst2[j] not in cache or cache[lst2[j]] == 0:
return False
cache[lst2[j]] -= 1
return True

print('Powerset Tests')
test_count = [0, 0]

def test():
example = powerset('abc')
return (example is not None and lists_matching(example,
['', 'a', 'b', 'c', 'ab', 'bc', 'ac', 'abc']))

expect(test_count, 'should work on example input abc', test)

def test():
example = powerset('')
return example is not None and lists_matching(example, [''])

expect(test_count, 'should work on empty input', test)

def test():
example = powerset('ab')
return (example is not None and
lists_matching(example, ['', 'a', 'b', 'ab']))

expect(test_count, 'should work on two-letter input', test)

def test():
example = powerset('abcdefg')
solution = ['', 'g', 'f', 'fg', 'e', 'eg', 'ef', 'efg', 'd', 'dg', 'df',
'dfg', 'de', 'deg', 'def', 'defg', 'c', 'cg', 'cf', 'cfg',
'ce', 'ceg', 'cef', 'cefg', 'cd', 'cdg', 'cdf', 'cdfg', 'cde',
'cdeg', 'cdef', 'cdefg', 'b', 'bg', 'bf', 'bfg', 'be', 'beg',
'bef', 'befg', 'bd', 'bdg', 'bdf', 'bdfg', 'bde', 'bdeg',
'bdef', 'bdefg', 'bc', 'bcg', 'bcf', 'bcfg', 'bce', 'bceg',
'bcef', 'bcefg', 'bcd', 'bcdg', 'bcdf', 'bcdfg', 'bcde',
'bcdeg', 'bcdef', 'bcdefg', 'a', 'ag', 'af', 'afg', 'ae',
'aceg', 'acef', 'acefg', 'acd', 'acdg', 'acdf', 'acdfg',
'acde', 'acdeg', 'acdef', 'acdefg', 'ab', 'abg', 'abf', 'abfg',
'abe', 'abeg', 'abef', 'abefg', 'abd', 'abdg', 'abdf', 'abdfg',
'abde', 'abdeg', 'abdef', 'abdefg', 'abc', 'abcg', 'abcf',
'abcfg', 'abce', 'abceg', 'abcef', 'abcefg', 'abcd', 'abcdg',
'abcdf', 'abcdfg', 'abcde', 'abcdeg', 'abcdef', 'abcdefg']
return example is not None and lists_matching(example, solution)

expect(test_count, 'should work on longer input', test)

print('PASSED: ' + str(test_count[0]) + ' / ' + str(test_count[1]) + '\n\n')


• input is a library function. Use a different variable name.
• Python comes with the methods itertools.combinations, which can generate all combinations of given size.

The function can be compressed to:

from itertools import combinations

def powerset(input_set):
result = []
for size in range(len(input_set) + 1):
result += combinations(input_set, size)
return result


If you want the result to be strings, instead of tuples of combinations; use a join:

result += [''.join(c) for c in combinations(input_set, size)]


Use the unittest module to write/generate test cases. The current method you've been following [1] [2] is neither maintainable nor readable in the long run!