Generate All Subsets of a Set Problem

Generate ALL possible subsets of a given set. The set is givet in the form of a string s containing distinct lowercase characters 'a' - 'z'.

Example

Input: "xy" 

Output: ["", "x", "y", "xy"] 

Notes

Input Parameters: There is only one argument denoting string s.

Output: Return array of strings res, containing ALL possible subsets of given string. You need not to worry about order of strings in your output array. E.g. s = "a", arrays ["", "a"] and ["a", ""]  both will be accepted.

Order of characters in any subset must be same as in the input string. For s = "xy", array ["", "x", "y", "xy"] will be accepted, but ["", "x", "y", "yx"] will not be accepted. 

Constraints:

• 0

• s only contains distinct lowercase alphabetical letters ('a' - 'z').

Empty set is a subset of any set.

Any set is a subset of itself.

Solution

We have provided 2 solutions:

1) Recursive Solution : other_solution.cpp.

2) Iterative Solution : optimal_solution.cpp.

Have a look at both the solutions. 

Both solutions are valid, but the recursive solution is slightly slower because of function calls and variable passing.

Also you should observe that the number of subsets will always be a power of 2, specifically 2^|s|.

Time Complexity:

O(2^n * n).

As we will generate 2^n strings of length O(n).

Auxiliary Space Used:

O(2^n * n).

As we will store 2^n strings of length O(n) in the output array to be returned.

Space Complexity:

O(2^n * n).

As auxiliary space used is O(2^n * n) and input is O(n) hence O(2^n * n) + O(n) -> O(2^n * n).

// -------- START --------

vector generate_all_subsets(string s)
{
	int n = s.length();
	vector all_subsets;
	// Base case when n = 0 i.e. s = "".
	all_subsets.push_back("");
	/*
	Suppose s = "xyz".
	Now try to find pattern in following steps (think how any step is related to previous step!):
	- [""]
	- ["", "x"]
	- ["", "x", "y", "xy"]
	- ["", "x", "y", "xy", "z", "xz", "yz", "xyz"]
	Let me explain what we have done in last step.
	First take array from previous step, that is ["", "x", "y", "xy"], append 'z' to each string, 
	that is ["z", "xz", "yz", "xyz"], now merge it with array in previous step! 
	*/
	for (int i = 1; i <= n; i++)
	{
		int old_len = all_subsets.size();
		for (int j = 0; j < old_len; j++)
		{
			/*
			Note that we are doing push_back that is adding value at the end of array, so we 
			already have the old values stored in it.
			*/
			all_subsets.push_back(all_subsets[j] + s[i - 1]);
		}
	}
	return all_subsets;
}

// -------- END --------