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