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 (

Time complexity: O(N * 2^N) to generate all subsets and then copy them into output list.powerset) of a set {1,2,3,4}

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; }