Power Set

Get started

🙏
জয় শ্রী রাম
🕉

Problem Statement:

Given an integer array nums, return all possible subsets (the power set). The solution set must not contain duplicate subsets.

Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

Example 2:
Input: nums = [0]
Output: [[],[0]]

Solution:

This chapter is the result of my intensive research on Combinatorial Algorithms. I will be covering several ways to generate Power Set. Not all of them are Backtracking approach. Please spend enough time on this chapter to get each of the concepts by heart, because each of the concepts discussed in this chapter could be used to solve wide range of different Combinatorial Problems.

Below are some of the approaches we could use to generate Power Set:

Concept of Inclusion and Exclusion using Boolean Array (My personal favorite and super easy and heavily reusable concept to solve Combinatorial problems using Backtracking):

For every element in the given array or list, we have choice to either include or not include it in a subset. Powerset is the exhaustive set of subsets which contain all the possible subsets, which means, we get powerset by making all possible choices for all given elements. Does this sound like an exhaustive search ? Yes, of course it does, which means we would be able to solve this problem using backtracking.

Backtrack approach
For each element nums[i] we have option to either include or exclude it from current subset and for each of these two choices for nums[i] we consider all combinations of the choice of inclusion and exclusion for the rest of the elements in given array nums[].

This helps us getting all the combinations starting from the combination where we choose to exclude all the elements to the combination where we choose to include all the elements and every combinations in between.

Java Code:

Python Code:

Binary Number Sequence from 0 to (2^N - 1):

Binary representation is the key to solving all subset generation problems.
To generate power set for N elements, simply count from 0 to 2^N - 1. Use the 0's and 1's in the binary numbers to form the subsets. 1 at index i of the binary number would indicate that element nums[i] is included in the subset, whereas 0 at index i would mean nums[i] is excluded.

Let's take an example:
input = {1, 2, 3}

000 -> since all are 0's, this indicates that none of the elements would be present in the subset, so the subset we get is [] which is an empty array
001 -> we get subset [3] since only index 2 (0-based indexing) has 1 and nums[2] = 3
010 -> we get subset [2] since only index 1 (0-based indexing) has 1 and nums[1] = 3
011 -> we get subset [2, 3] since index 1 and 2 have 1 and nums[2] = 3
100 -> we get subset [1] since index 1 (0-based index) has 1 and nums[2] = 3
101 -> we get subset [1, 3]
110 -> we get subset [1, 2]
111 -> we get subset [1, 2, 3] since we have 1's in all three places

Above algorithm could be solved in below two ways:

Implementation #1:

Java Code:

Python Code:

Implementation #2:

Java Code:

Python Code:

Gray Code Sequence of size N:

The gray code is a binary numeral system where two successive values differ in only one bit. A gray code sequence must begin with 0.

How to create sequence of Gray Code ?
Gray Code sequence of length N starts at 0 and ends at (2^N - 1).

Gray Code sequence of length 1 is as follows:

0
1

Gray Code sequence of length 2 is as follows:

Gray Code sequence of length 3 is as follows:

The above sequences are Gray Codes of different widths. Following is an interesting pattern in Gray Codes. n-bit Gray Codes can be generated from list of (n-1)-bit Gray codes using following steps.

Let the list of (n-1)-bit Gray codes be L1. Create another list L2 which is reverse of L1.
Modify the list L1 by prefixing a ‘0’ in all codes of L1.
Modify the list L2 by prefixing a ‘1’ in all codes of L2.
Concatenate L1 and L2.
The concatenated list is required list of n-bit Gray codes.
For example, following are steps for generating the 3-bit Gray code list from the list of 2-bit Gray code list.
L1 = {00, 01, 11, 10} (List of 2-bit Gray Codes)
L2 = {10, 11, 01, 00} (Reverse of L1)
Prefix all entries of L1 with ‘0’, L1 becomes {000, 001, 011, 010}
Prefix all entries of L2 with ‘1’, L2 becomes {110, 111, 101, 100}
Concatenate L1 and L2, we get {000, 001, 011, 010, 110, 111, 101, 100}

To generate n-bit Gray codes, we start from list of 1 bit Gray codes. The list of 1 bit Gray code is {0, 1}. We repeat above steps to generate 2 bit Gray codes from 1 bit Gray codes, then 3-bit Gray codes from 2-bit Gray codes till the number of bits becomes equal to n.

Now let's see how we would use Gray Code sequence to compute Power Set.

For a given array nums[] with n elements we generate a valid sequence of gray code with n number of bits in the gray code.

Presence of 1 at the index i of the gray code would mean nums[i] is included in the current subset, and presence of 0 at index i of gray code would mean that nums[i] is excluded from the current subset.

Let's take an example: input = {1, 2, 3}

Gray Code:
000 -> since all are 0's, this indicates that none of the elements would be present in the subset, so the subset we get is [] which is an empty array
001 -> we get subset [3] since only index 2 (0-based indexing) has 1 and nums[2] = 3
011 -> we get subset [2, 3] since index 1 and 2 have 1 and nums[2] = 3
010 -> we get subset [2] since only index 1 (0-based indexing) has 1 and nums[1] = 3
110 -> we get subset [1, 2]
111 -> we get subset [1, 2, 3] since we have 1's in all three places
101 -> we get subset [1, 3]
100 -> we get subset [1] since index 1 (0-based index) has 1 and nums[2] = 3

Java Code:

Python Code:

Lexicographic Order:

Lexicographic Order means sorted order and is often the most natural way to generate combinatorial objects. The power set for [1, 2, 3] in lexicographic order are [ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ].

It is very important that you are well versed with the important utility methods introduced in Backtracking Algorithm such as isACompleteSolution, constructCandidates(partialSolution, index) , makeMove(partialSolution, index), backtrack(…) and undoMakeMove(partialSolution, index) because our solution would be based on reusing these methods and you would be very easily able to get the algorithm if you have a strong grasp on the Backtracking template. My goal is also to show you how all Backtracking problem could be solved by using the template discussed in Backtracking Algorithm

The first step of designing our Backtracking algorithm would be to take a small example and see what's going on there:

input = [1,2,3]
output=[ [], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3] ]

Let's rearrange the output a bit to be able to see any pattern present there. This is super important for most Backtracking problems. Please do not underestimate the power of observation or the ability to identify any useful pattern present in the given problem.

[1]      [2]   [3]  []
[1,2]    [2,3]
[1,2,3]
[1,3]

So we see the largest subset in the powerset is the given input itself, for example for input = [1, 2, 3] the largest subset in the powerset is [1, 2, 3]) and the smallest subset is of length 0 since [] is the smallest subset. The length of the subsets in the powerset ranges from 0 to length(input array) including every length possible in [0, input.length].

For a given array nums[] of length n, we have subsets starting with nums[i] for all i = 0 to (n - 1). We get subsets starting with nums[i] by computing all subsets for nums[(i + 1)...(n - 1)] and then prepending nums[i] to each of them. We get the Power Set by computing all subsets for all nums[i], i = 0 to (n - 1).

For example, if input = [1, 2, 3] we can do below:
When we are at index = 0:
Power Set of [2, 3] is [[2], [3], [2, 3], []].
Now we prepend i to each of it => [[1, 2], [1, 3], [1, 2, 3], [1]]

When we are at index = 1: Powerset of [3] is [[], [3]]
Prepending 2 we get => [[2], [2, 3]]

When we are at index = 2:
Powerset = [3] since index = 2 is the right most index.

Overall Powerset = [[1, 2], [1, 3], [1, 2, 3], [1], [2], [2, 3], [3], []]

Using the discussion above and the Backtracking Template we have handy we would easily be able to come up with the below code.

Java Code:

Python Code:

Time Complexity:

We are calling Backtrack(...) method (which itself is O(N) (because of the O(N) for-loop / while-loop)) O(N) time. So overall time complexity = O(N^N), where N = length of the input[].

Backtracking algorithms are exponential in time, since we have to do an exhaustive search.

Space Complexity:

Since we have O(N^N) recursion call, space complexity = O(N^N) since O(N^N) recursion call takes O(N^N) space in call stack.

Don't forget to take an in-depth look at the other backtracking problems in the below link, because that is what would make you comfortable with using the backtracking template and master the art of Backtracking and be an over-achiever:

All Backtracking Problems in one place

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

AWS | Microsoft | University of Florida

View LinkedIn profile

Power Set

জয় শ্রী রাম

Problem Statement:

Solution:

Concept of Inclusion and Exclusion using Boolean Array (My personal favorite and super easy and heavily reusable concept to solve Combinatorial problems using Backtracking):

Java Code:

Python Code:

Binary Number Sequence from 0 to (2N - 1):

Implementation #1:

Java Code:

Python Code:

Implementation #2:

Java Code:

Python Code:

Gray Code Sequence of size N:

Java Code:

Python Code:

Lexicographic Order:

Java Code:

Python Code:

Time Complexity:

Space Complexity:

Instructor:

Abhishek Dey

Senior SDE | Chief Architect

AWS | Microsoft | University of Florida

Binary Number Sequence from 0 to (2^N - 1):