Monday, December 15, 2014

All Subsets

The following Python program generates all ordered subsets of a list. This method is very useful in brute-force approach of solving a problem
def generateSubsets(A, n, sub=[]):
    if n == 0:
        print(sub)
        return
    generateSubsets(A, n-1, sub)
    generateSubsets(A, n-1, [A[n-1]] + sub)

A = list(map(int, input().split()))
generateSubsets(A, len(A))
Input:
1 2 3 4

Output:
[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]
[4]
[1, 4]
[2, 4]
[1, 2, 4]
[3, 4]
[1, 3, 4]
[2, 3, 4]
[1, 2, 3, 4]

No comments:

Post a Comment