Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.

Subsets (Power Set)

Problem Statement

You are given an integer array, nums, with all unique elements. Return all possible subsets of nums — this is also called the power set.

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

Examples

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]]

Constraints

• 1 ≤ nums.length ≤ 10
• −10 ≤ nums[i] ≤ 10
• All the numbers in nums are unique.

Solution

This solution uses a neat trick with binary numbers (bitmasking).

The Main Idea

• If nums has n elements, there are exactly 2ⁿ possible subsets. This is because for each element, we have two choices: include it or don't include it.
• We can represent every possible subset using a number from 0 to 2ⁿ - 1, written in binary. Each bit in this number tells us whether to include the element at that position.

For example, if nums = [1, 2, 3] and we look at the number 2, which is 010 in binary:

• The rightmost bit (position 0) is 0 → don't include nums[0].
• The middle bit (position 1) is 1 → include nums[1].
• The leftmost bit (position 2) is 0 → don't include nums[2].

So the number 2 (binary 010) represents the subset [2] (since nums[1] = 2).

Steps

• We loop through every number i from 0 to 2ⁿ - 1. Each of these numbers represents one possible subset.
• For each number i, we check every bit position j (from 0 to nums.length - 1):
  • We use a helper function, getBit(num, bit), to check if the bit at position j is 1 or 0.
  • If the bit is 1, we include nums[j] in the current subset.
• Once we've checked all bit positions for a given i, we've built one full subset. We add it to our results.
• We repeat this for every number from 0 to 2ⁿ - 1, which gives us every possible subset.

How getBit Works

The getBit function checks whether a specific bit position in a number is 1 or 0:

• It shifts the number 1 to the left by bit positions. This creates a number with a single 1 at exactly the position we want to check.
• It then performs an AND operation between this shifted number and our original number.
• If the result is not zero, that bit position is 1. Otherwise, it's 0.

Code

function getBit(num, bit) {
  let temp;
  temp = 1 << bit;
  temp = temp & num;

  if (temp === 0) {
    return 0;
  }

  return 1;
}

function findAllSubsets(nums) {
  let sets = [];

  if (nums.length === 0) {
    return [[]];
  } else {
    let subsetsCount = 2 ** nums.length;
    for (let i = 0; i < subsetsCount; i++) {
      let subset = new Set();
      for (let j = 0; j < nums.length; j++) {
        if (getBit(i, j) == 1 && !subset.has(nums[j])) {
          subset.add(nums[j]);
        }
      }

      if (i === 0) {
        sets.push([]);
      } else {
        sets.push(Array.from(subset));
      }
    }
  }
  return sets;
}