CareerCup

/*
Solution:
- the powerset is the set of all subsets
- all or no element can be part of and all combination
- per element two possibilities: be part of or not, 2 elements
  so 2^n possibilities

How to compute:
lets assume the set is given as a string:
*/

#include <iostream>
#include <string>

using namespace std;

void printPowersetRec(const string& prefix, 
					  const string& remaining)
{
	
	if(remaining.length() == 0) 
	{ 
		cout << "{" << prefix << "} ";
	}
	else 
	{
		string newRemaining = remaining.substr(1);
		string newPrefix = prefix;
		newPrefix.append(1, remaining[0]);
		printPowersetRec(prefix, newRemaining); // included
		printPowersetRec(newPrefix, newRemaining); // excluded
	}	 
}

void printPowerset(const string& input)
{
	printPowersetRec("", input);
}

int main()
{
	printPowerset("ABCD");
}

/* 
  ZoomBA powerset is simply done by 
  the following 
*/
my_vals = [ 0, 1, 2, 3 ]
// sequences() function generates all possible sub sequences
// which is the power set :) 
fold ( sequences(my_vals) ) -> { println($.o) }

// in a sensible way, this is how you can do the same
// also explains why it is Theta( 2^n )
def power_set( arr ){
  len = size( arr ) 
  n = 2 ** len
  for ( bn : [0:n] ){ // this is why it is 2^n 
    bs = str( bn, 2 ) // binary string format 
    // to make it sized n binary digits 
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
    // select the index i's item when bs contains 1 at index i 
    subseq = list( bs.value ) -> { continue( $.o == _'0' ) ; arr[$.i] }
    println ( subseq )
  } 
}
power_set( my_vals )

A much cleaner way in ZoomBA :

my_vals = [ 0, 1, 2, 3 ]
// minimizing use of English and more math 
def power_set( arr ){
  len = size( arr ) 
  // this is why it is 2^n 
  list ( [0 : 2 ** len ] ) -> { 
    bs = str( $.o , 2 ) // binary string format 
    // to make it sized n binary digits 
    bs = ( '0' ** ( len - size(bs) ) ) + bs // pad 0's to the left 
    // select the index i's item when bs contains 1 at index i 
    select( bs.value ) :: { $.o == _'0' } -> { arr[$.i] }
  } 
}
println ( power_set( my_vals ) )

In your solution it is actually O(2^n+1), the one below is O(2^n) with better space complexity as well

vector<string> subsets = {""};
	cout << "{ } ";
	for (auto ch : input) {
		auto len = subsets.size();
		for (auto i = 0u; i < len; i++) {
			auto s = subsets[i] + ch;
			subsets.push_back(s);
			cout << "{" << s << "} ";
		}
	}

Not sure if this will now post twice or if my first post did not make it. The recursive C++ solution, shown here, actually has complexity of O(2^n+1). The iterative solution below is O(2^n) with lesser space complexity.

void printPowerset2(string input) {	
	vector<string> subsets = {""};
	cout << "{ } ";
	for (auto ch : input) {
		auto len = subsets.size();
		for (auto i = 0u; i < len; i++) {
			auto s = subsets[i] + ch;
			subsets.push_back(s);
			cout << "{" << s << "} ";
		}
	}
}

The normal iterative approach:

def power_set(inp_set):
	result = [[]]

	for ele in inp_set:
		newSubSets = [subset + [ele] for subset in result] # this step is responsible for combining each element to every other element in the already existing power set
		result.extend(newSubSets)

	return result

The most famous bit manipulation technique

def power_set3(inp_set):
	pwr_set_size = 2 ** len(inp_set)
	pwr_set = [[]]

	for i in range(pwr_set_size):
		new_set = []
		for j in range(len(inp_set)):
			if i & 1 << j : # this is to check if the jth bit is set or not
				new_set.extend([inp_set[j]])

		pwr_set.append(new_set)
	
	return pwr_set

There could be a recursive definition which is a little tricky:

def power_set2(inp_set, new_set):
	if inp_set == []:
		return [new_set]
	else:
		result = []
		for ele in power_set2(inp_set[1:],new_set + [inp_set[0]]): # generate all subsets which has the first element
			result.append(ele)

		for ele in power_set2(inp_set[1:], new_set): #generate all the subsets which does not contain the first element
			result.append(ele)

		return result

static List<List<Integer>> subset(int n) {
        
        List<List<Integer>> A = new ArrayList<>();
        
        if( n == 0 ) return A;
        
        List<Integer> S = new ArrayList<>();
        
        for(int i = 1;i <= n; i++) {
            S.add(i);
            dfsSubset(i, S, A, n);
            Integer tmp = S.remove(S.size()-1);
        }
        
        
        return A;
    }
    
    static void dfsSubset(int x, List<Integer> S, List<List<Integer>> A, int n){
        
        //process what we have
        List<Integer> tmpA = new ArrayList<>();
        for(Integer v : S){
            tmpA.add(v);
            System.out.print(v+" ");
            
        }
        System.out.println();
        
        A.add(tmpA);
        
        
        for(int i = x+1;i<=n;i++) {
            S.add(i);
            dfsSubset(i, S, A, n);
            Integer tmp = S.remove(S.size()-1);
        }
    }

To prove the complexity, use geometric series sum
Here is the logic

public class Set
{
	public List<string>() setStrings;
	// Constructors and all will come here.
	
	public void PrintPowerSet()
	{
		// Error conditions such as setStrings is null or does not any data will come here
		LinkedList<Set> powerSet = new LinkedList<Set>();
		powerSet.AddFirst(new Set(this.setStrings); // adding the first element
		foreach(var element in this.setStrings)
		{
			var enumerator = powerSet.GetEnumerator();
			while(enumerator.MoveNext())
			{
				powerSet.AddFirst(new Set(enumerator.Current.setStrings.Remove(element)); // adding the first element
			}
		}
		var enumerator = powerSet.GetEnumerator();
		while(enumerator.MoveNext())
		{
			Print(enumerator.Current);
		}
	}
}

public void Print(Set set)
{
	Console.WriteLine("{" + set.setStrings + "}");
}

Now complexity of this is 2^0 + 2^1 + 2^2.....2^n-1 = 2^n as per Geometric Series. so the time complexity is O(2^n), space complexity is O(2^n) because, we are storing all the data here PROVIDED that removing an entry from the list take only constant time, which i doubt :).

Many people posted their answers. But, I'm surprised that no one asked the question, do we have duplicates in the original array.

def find_subsets(input, i):
    # Use i as a binary mask to select which elements to include in the set.
    bitfield = list(bin(i))[2:]

    idx = len(input) -1

    res = []

    while(i > 0):
        if i%2 == 1:
            res.append(input[idx])
        i = i //2
        idx -= 1

    return res


input = [1, 2, 3, 4, 5, 6]

n = len(input)
subsets = []
for i in range(2**n):
    subsets.append(find_subsets(input, i))

print(subsets)