Solution: Subsets

Let's solve the Subsets problem using the Subsets pattern.

We'll cover the following

Statement

Given an array of integers, nums, find all possible subsets of nums, including the empty set.

Note: The solution set must not contain duplicate subsets. You can return the solution in any order.

Constraints:

  • 1≤1 \leq nums.length ≤10\leq 10
  • −10≤-10 \leq nums[i] ≤10\leq 10
  • All the numbers of nums are unique.

Pattern: Subsets

Problems such as this one, where we need to find all possible subsets of a given set, can be efficiently solved using the subsets pattern. This pattern involves generating all possible subsets of a given set by using binary representations of indices to represent which elements should be included in each subset. This approach allows us to solve a wide range of problems that involve generating all possible subsets of a set.

Solution

Generating all possible subsets of a given set inherently involves exploring different combinations of elements, which aligns well with the subset technique. First, the total number of potential subsets is calculated using: 2nums.length2^{nums.length}. This determines the total number of possible combinations, where each combination represents a potential subset formed by either including or excluding each element from the input list. Next, we iterate through all potential possible combinations of subsets starting from 0 and iterating up to the total number of subsets calculated earlier. A new subset is generated within each iteration by interpreting the current iteration number in binary format. Each bit of the binary representation corresponds to whether the element at that position in the input list should be included in the subset. We use bitwise operations to check each bit of the binary representation. If the bit is set to 1, the corresponding element from the input list is included in the subset. Otherwise, it is excluded. This approach ensures that every possible combination of elements is considered, generating all subsets without duplicates.

Note: The ordering of bits for picking integers from the set doesn’t matter. We can pick integers from left to right and produce the same output as picking integers from right to left.

Note: In the following section, we will gradually build the solution. Alternatively, you can skip straight to just the code.

Step-by-step solution construction

The first step in solving this problem is calculating the total subsets generated from the given numbers. The total number of possible subsets for a set of size nn is 2n2^n. We’ll use this formula to calculate the total subsets for our input numbers.

import java.util.*;
class FindSubsets {
	static List<List<Integer>> findAllSubsets(int[] nums) {
		List<List<Integer>> setsList = new ArrayList<>();
		if (nums.length != 0) {
			
			// finds number of subsets by taking power of length of input array
			int subsetsCount = (int) (Math.pow(2, nums.length));
			System.out.println("   Total subsets: "+ subsetsCount);
		} else {
			System.out.println("   Total subsets: 1");
			List<Integer> subset = new ArrayList<>();
			setsList.add(subset);
		}
		return setsList;
	}
	public static void main(String[] args) {
        int[][] inputSets = {
                {},
                {2, 5, 7},
                {1, 2},
                {1, 2, 3, 4},
                {7, 3, 1, 5}
        };
        for (int i = 0; i < inputSets.length; i++) {
            int[] set = inputSets[i];
            System.out.println((i + 1) + ". Set: " + Arrays.toString(set));
            List<List<Integer>> subsets = findAllSubsets(set);
			System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Subsets

Once we have the count of all possible subsets, we can generate each subset using a binary representation of the indices. We will initiate a loop from i = 0 to i = subsetsCount - 1, where subsetsCount represents the total subsets. In each loop iteration, we will form a subset using the value of i as a bitmask.

Using i as a bitmask enables us to represent which elements from the original set should be included in the current subset. The set bits in i correspond to the indices of the elements to choose from the original set. For example, consider a set [1, 2, 3] and i = 2. In binary representation, 22 is denoted as 010. Since the second bit is set to 11, our subset will include the second element from the original set, which is 22. Therefore, the subset will be [2]. Similarly, for i = 3, the binary representation is 011. In this case, the set bits in i correspond to the first and second elements from the original set, resulting in the subset [1, 2]. Within each iteration of the loop (from 00 to subsetsCount - 1), we will perform the following steps:

  • We will initialize an empty set called subset to store the subset being constructed.

  • During each iteration, we will iterate over the set nums elements using the variable j, representing the indices of the elements in nums.

  • For each j, we will call the getBit(i, j) function to determine if the jthj^{th} bit of i is set to 11.

  • If getBit(i, j) returns 11, indicating that the jthj^{th} bit is set to 11, and nums[j] is not already present in subset, we will add nums[j] to subset.

  • Finally, we will add the set subset to setsList.

Once the loop completes, the list setsList will contain all the subsets, including the empty set. This approach allows us to generate all possible subsets of the given set by considering each possible combination of elements using the binary representation of the indices.

import java.util.*;
class FindSubsets {
	static int getBit(int num, int bit) {
		// shifts the first operand the specified number of bits to the left
		int temp = (1 << bit);
		// if binary number and current subset count are equal,
		// return 1 else return 0
		temp = temp & num;
		if (temp == 0) {
			return 0;
		}
		return 1;
	}
	static List<List<Integer>> findAllSubsets(int[] nums) {
		List<List<Integer>> setsList = new ArrayList<>();
		if (nums.length != 0) {
			// finds number of subsets by taking power of length of input array
			int subsetsCount = (int) (Math.pow(2, nums.length));
			for (int i = 0; i < subsetsCount; ++i) {
				// Set is created to store each subset
				List<Integer> subset = new ArrayList<>();
				for (int j = 0; j < nums.length; ++j) {
					// if a specific bit is 1, chooses that number from the original set
					// and add it to the current subset
					if (getBit(i, j) == 1) {
						int x = nums[j];
						subset.add(x);
					}
					
				}
				System.out.println("\tCurrent generated subset: "+ subset.toString());
				// all subsets are now pushed back in the hah set list
				setsList.add(subset);
				System.out.println("\tSubsets list: "+ setsList.toString()+"\n");
			}
		} else {
			List<Integer> emptySet = new ArrayList<>();
			setsList.add(emptySet);
		}
		return setsList;
	}
    public static void main(String[] args) {
        int[][] inputSets = {
                {},
                {2, 5, 7},
                {1, 2},
                {1, 2, 3, 4},
                {7, 3, 1, 5}
        };
        for (int i = 0; i < inputSets.length; i++) {
            int[] set = inputSets[i];
            System.out.println((i + 1) + ". Set: " + Arrays.toString(set));
            List<List<Integer>> subsets = findAllSubsets(set);
            System.out.println("   Subsets: " + subsets);
			System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Subsets

Just the code

Here’s the complete solution to this problem:

import java.util.*;
class FindSubsets {
	static int getBit(int num, int bit) {
		int temp = (1 << bit);
		temp = temp & num;
		if (temp == 0) {
			return 0;
		}
		return 1;
	}
	static List<List<Integer>> findAllSubsets(int[] nums) {
		List<List<Integer>> setsList = new ArrayList<>();
		if (nums.length != 0) {
			int subsetsCount = (int) (Math.pow(2, nums.length));
			for (int i = 0; i < subsetsCount; ++i) {
				List<Integer> subset = new ArrayList<>();
				for (int j = 0; j < nums.length; ++j) {
					if (getBit(i, j) == 1) {
						int x = nums[j];
						subset.add(x);
					}
					
				}
				setsList.add(subset);
			}
		} else {
			List<Integer> emptySet = new ArrayList<>();
			setsList.add(emptySet);
		}
		return setsList;
	}
    public static void main(String[] args) {
        int[][] inputSets = {
                {},
                {2, 5, 7},
                {1, 2},
                {1, 2, 3, 4},
                {7, 3, 1, 5}
        };
        for (int i = 0; i < inputSets.length; i++) {
            int[] set = inputSets[i];
            System.out.println((i + 1) + ". Set: " + Arrays.toString(set));
            List<List<Integer>> subsets = findAllSubsets(set);
            System.out.println("   Subsets: " + subsets);
			System.out.println(new String(new char[100]).replace('\0', '-'));
        }
    }
}
Subsets

Solution summary

To recap, the solution to this problem can be divided into the following parts:

  1. Calculate the subsets count using the formula 2n2^n.
  2. Iterate from 00 to the subsets count.
  3. Generate subsets using bitwise operations.
  4. Add each generated subset to the list of subsets.
  5. Return the list of subsets.

Time complexity

The time complexity of this solution is exponential, specifically O(2n⋅n)O(2^n \cdot n), where nn represents the number of integers in the given array.

Space complexity

The space complexity of this solution is O(n)O(n), where nn represents the number of integers in the given array. This analysis excludes the space utilized by the output array, setsList, and only considers the space used by the subset set.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.