Instantly share code, notes, and snippets.

@tamim /allsubsets.py
Last active Oct 30, 2018

Embed
What would you like to do?
Python code to generate all subsets of a set.
"""
Generate all subsets of a set using recursion
"""
def subsets1(S):
if S == []:
return [[]]
result = [[]]
n = len(S)
visited = [False] * n
def recurse(i, n, li):
if i == n:
return
if len(li) > 0:
result.append([x for x in li])
for j in range(i, n):
if visited[j]:
continue
visited[j] = True
li.append(S[j])
recurse(j, n, li)
li.pop()
visited[j] = False
recurse(0, n, [])
return result
"""
Generate all subsets of a set without using recursion
"""
def subsets2(S):
if S == []:
return [[]]
result = [[]]
while len(S):
temp_r = []
x = S.pop()
for r in result:
temp_r.append(r + [])
temp_r.append(r + [x])
result = [item for item in temp_r]
return result
if __name__ == "__main__":
print(subsets1([1, 2, 3]))
print(subsets2([1, 2, 3]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment