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'.
Input: "xy"
Output: ["", "x", "y", "xy"]
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.
• 0 <= |s| <= 20
• s only contains distinct lowercase alphabetical letters ('a' - 'z').
Empty set is a subset of any set.
Any set is a subset of itself.
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|.
O(2^n * n).
As we will generate 2^n strings of length O(n).
O(2^n * n).
As we will store 2^n strings of length O(n) in the output array to be returned.
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).