# Leetcode – 78. Subsets

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 – {[], }. Now pick the second element from list ex. 3, now you have another 2 sets – {[], }. Merge 3’s sets with 4’s sets. Which will generate total of 4 sets {[],,,[3,4]}.

Now pick the next element, i.e 2, now you have another 2 sets – {[], } and merge them to previous 4 sets. This will generate total of 8 sets {[],,,[3,4] , ,[2,3],[2,4],[2,3,4]}

Similarly, pick the last element, i.e 1, now you have another 2 sets – {[], } and merge them to previous 8 sets. This will generate total of 16 sets {[],,,[3,4], ,[2,3],[2,4],[2,3,4], ,[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>>();

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)
{