Subsets with a Catch

Computer Science Level 4

In his programming class, Rishabh is asked to implement a program that takes in a set $S$ of $n$ distinct integers and output all possible subsets of $S$ .

However, the catch is that he is asked not to use recursive functions.

Using which data structure makes more sense for Rishabh to solve this problem?

Binary Search Tree Hash Table Queue Stack

1 solution

Agnishom Chattopadhyay
Aug 17, 2016

The natural way to answer this problem is this:

The power set of the empty set is just $\left \{ \phi \right \}$ .
Otherwise, we can choose whether the first element is in a particular set or isn't and then we've reduced the problem to a set with $n-1$ elements.

def subsets(L):
    if L == []:
        return [[]]
    setsWithX = []
    setsWithoutX = []
    for l in subsets(L[1:]):
        setsWithX.append([L[0]] + l)
        setsWithoutX.append(l)
    return setsWithX + setsWithoutX

Since function calls themselves are implemented within the memory using a stack, it is possible to use stacks to implement the behaviour of recursion.

Subsets with a Catch

1 solution

0 pending reports