There are two direction for us to solve this problem.
(1) Recursion
Recursive step: T[0] conbines with findsubsets(T[1:])
Final step: if len(T)==0: return [[]]
Code:
#Recursive method def findsubsets(T): if len(T)==0: return [[]] answer=[] for sets in findsubsets(T[1:]): answer.append(sets) new=sets[:]+[T[0]] answer.append(new) return answer
(2) Noncursive method
In this method, we can use stack and queue to help us solve this problem.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Algorithm:
Input: an n-element set T
Output: all the subsets of T
1. define an empty stack S
2. define an empty queue Q
3. S.push([])
4. S.push([T[0]])
5. for all the elements a in T[1:]:
6. while S is not empty:
7. x=S.pop()
8. Q.enqueue(x)
9. x=x+[[a]]
10. Q.enqueue(x)
11. if a is not the final element in T:
12. while Q is not empty:
13. S.push(Q.dequeue())
14. return Q
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Code:
def findsubsets2(T):
Q=ArrayQueue()
S=ArrayStack()
S.push([])
S.push([T[0]])
for i in T[1:]:
while (len(S)!=0):
x=S.pop()
Q.enqueue(x)
x=x+[[i]]
Q.enqueue(x)
if i!=T[-1]:
while (len(Q)!=0):
S.push(Q.dequeue())
return Q._data
[Algorithm] How to find all the subsets of an n-element set T?
原文：https://www.cnblogs.com/chiyeung/p/9689591.html