Aggregating subsets of an array-CodePudding

I am working on a problem to find and aggregate subsets of an array. After few tries, I was able to print all the subsets one after another using following approach:

def print_subsets(arr, curr, idx):

    if idx == len(arr):
        print(curr)
        return
    print_subsets(arr, curr, idx   1)
    print_subsets(arr, curr   [arr[idx - 1]], idx   1)

For example if we have function call; print_subsets([1,2], [], 0) we get output as [],[1],[2],[1,2].

Next step, is it possible to use modified recursive approach and return the output as a list containing all subsets of this array?

Expected output: [[],[1],[2],[1,2]].

CodePudding user response：

Assuming your code correctly prints the desired sub-lists you are almost there. You just need to return the sub-lists instead of printing them:

def print_subsets(arr, curr, idx):
    if idx == len(arr):
       return [curr]
    return print_subsets(...)   print_subsets(...)

(I put [] around curr because you want to return a list of sublists, not just the sublist).

So whenever a subset is identified (the recursion base case) instead of printing it the function returns it. Otherwise it just aggregates and returns the subsets returned by the recursive calls.

With that change I would rename the function to something like getSubsets(). I also recommend providing default values for curr and idx to simplify the initial call:

def getSubsets(arr, curr=[], idx=0):
    ...

Then you can call it as:

subsets = getSubsets(arr)

CodePudding user response：

You know you could use python built-in itertools instead:

import itertools as it

arr = [1,2]
subsets = [list(i) for c in range(len(arr) 1) for i in it.combinations(arr,c)]

output:

>> [[], [1], [2], [1, 2]]