Java solution to subsets/power-set FAANG interview questions

Key takeaways:

• A subset is any combination of elements from a set, and the power set is the collection of all subsets. For a set with $n$ elements, the power set contains $2^n$ subsets.

• Subsets are crucial in combinatorics and are used in problems like decision-making, finding combinations, and organizing data.

• Bitwise operations are used to generate the power set, determining element inclusion/exclusion through binary representation.

• Duplicates are avoided by sorting the array and skipping subsets with repeated elements.

• Time complexity is $O(2^n * n)$ and space complexity is $O(2^n * n)$ due to subset generation and storage.

A subset is any combination of elements from a given set, including the empty set and the set itself. The power set is the set of all possible subsets of a given set. For a set with $n$ elements, the power set contains $2^n$ subsets. Subsets/power sets are fundamental in combinatorics and are widely applicable in solving problems like:

• Decision-making processes (e.g., subset sums, knapsack problems).

• Finding combinations and arrangements.

• Data organization tasks (e.g., forming groups, partitions).

Problem statement of subsets/power-set

Write a program to find all possible subsets (the power set) of a given input array nums. The solution should ensure no duplicate subsets, even if the input array contains duplicates.

Example:

• Input: nums = [1, 2, 2, 2]

• Output: [[], [1], [1, 2], [1, 2, 2], [1, 2, 2, 2], [2], [2, 2], [2, 2, 2]]

• Explanation: According to the formula mentioned earlier, the total count of subsets is calculated as$2^4 = 16$However, the output shows only $8$ subsets because duplicate subsets are ignored.

Java solution to subsets/power-set

This program generates the power set of a given input array nums using bitwise operations. For a set with $n$ elements, there are $2^n$ possible subsets. Each subset can be formed by considering whether each element is included or excluded. Using bitwise operations, we can efficiently determine the inclusion or exclusion of elements for each subset in an iterative manner.

The process involves an outer loop controlled by a variable called counter, which iterates through all integers from 0 to $2^{n}-1$. The binary representation of the counter determines which elements are included in the current subset. The table below demonstrates how subsets are generated based on the binary values of counter.

Let’s look at the following illustration to get a better understanding of the solution:

Step-by-step algorithm:

Here is the step-by-step approach to generate all unique subsets.

1. Sort the input array:

   1. Sort nums to handle duplicates effectively.

   2. Sorting ensures that duplicates are adjacent, allowing us to skip them easily.

2. Initialize variables:

   1. Create an empty list result to store all subsets.

3. Iterate through all possible combinations:

   1. Compute the total number of subsets: subsetCount = 2^n or 1 << n (bitwise left shiftThe bitwise left shift operation (<<) shifts the bits of a number to the left by a specified number of positions. Each left shift multiplies the number by 2, effectively doubling its value.).

   2. For each integer counter from 0 to subsetCount - 1:

      1. Initialize an empty list currentSubset to build the current subset.

      2. Set a boolean isValid to true to track if this subset is valid (used for skipping duplicates).

      3. Check each bit:

         1. For each bit position i (from 0 to n−1):

            1. If the i-th bit of counter is set (counter & (1 << i) != 0):

               1. Check for duplicates:

                  1. If nums[i] == nums[i-1] and the i−1-th bit of counter is not set, mark isValid as false and break the loop.

               2. If no duplicates, add nums[i] to currentSubset.

4. Add valid subsets:

   1. If isValid is still true after the loop, add currentSubset to result.

5. Return the result:

   1. After processing all counter values, return the result list containing all subsets.

Check out this course on how to solve problems using bit manipulation: Master Bit Manipulation for Coding Interviews.

Let’s look at the code for the solution we just discussed.

Complexity analysis

The time complexity of the given solution is $O(2^n \cdot n)$. This is because there are $2^n$ possible subsets for an input array of size $n$, as each element can either be included or excluded. For each subset, the algorithm iterates through $n$ elements to check if a bit is set, resulting in a total time complexity of $O(2^n \cdot n)$. Additionally, the array is sorted initially to handle duplicates, which takes $O(n \log n)$. However, for large $n$, the $2^n$ term dominates, making the overall time complexity approximately $O(2^n \cdot n)$.

The space complexity of the solution is $O(2^n \cdot n)$. This accounts for the storage of all subsets in the result list, where each subset can have up to $n$ elements, and there are $2^n$ subsets. Temporary variables like currentSubset and the counter use negligible additional space. Thus, the dominant factor in space usage is the storage of subsets, resulting in a total space complexity of $O(2^n \cdot n)$.