Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Solution:
Cascading Approach: Lets say, we have a set S={1,2,3,4}.
Pick an element from set, ex. 4, now you have 2 sets – {[], [4]}. Now pick the second element from list ex. 3, now you have another 2 sets – {[], [3]}. Merge 3’s sets with 4’s sets. Which will generate total of 4 sets {[],[3],[4],[3,4]}.
Now pick the next element, i.e 2, now you have another 2 sets – {[], [2]} and merge them to previous 4 sets. This will generate total of 8 sets {[],[3],[4],[3,4] , [2],[2,3],[2,4],[2,3,4]}
Similarly, pick the last element, i.e 1, now you have another 2 sets – {[], [1]} and merge them to previous 8 sets. This will generate total of 16 sets {[],[3],[4],[3,4], [2],[2,3],[2,4],[2,3,4], [1],[1,3],[1,4],[1,3,4], [1,2],[1,2,3],[1,2,4],[1,2,3,4]}. These are final 16 sets generated (powerset) of a set {1,2,3,4}
Time complexity: O(N * 2^N) to generate all subsets and then copy them into output list.
Space complexity: O(N * 2^N) to keep all the subsets of length N, since each of N elements could be present or absent.
public static IList<IList<int>> Subsets(int[] nums)
{
IList<IList<int>> subsets = new List<IList<int>>();
subsets.Add(new List<int>());
for (int x = 0; x < nums.Length; x++)
{
List<List<int>> newSubsets = new List<List<int>>();
//Generate new sets - Mergeing nums[x] into previous 'subsets'
foreach (List<int> curr in subsets)
{
newSubsets.Add(curr.Concat(new List<int>() { nums[x] }).ToList());
}
foreach (List<int> curr in newSubsets)
{
subsets.Add(curr);
}
}
return subsets;
}