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 – {[], [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.
Cascading approach
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;
        }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s