Generate All Subsets Powerset in DSA Javascript - Time & Space Complexity

Time Complexity: Generate All Subsets Powerset

O(n * 2^n)

Understanding Time Complexity

When we generate all subsets of a set, we want to know how the time needed grows as the set gets bigger.

We ask: How does the work increase when the input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function generateSubsets(nums) {
  const result = [];
  function backtrack(start, subset) {
    result.push([...subset]);
    for (let i = start; i < nums.length; i++) {
      subset.push(nums[i]);
      backtrack(i + 1, subset);
      subset.pop();
    }
  }
  backtrack(0, []);
  return result;
}
    

This code finds all possible subsets (the powerset) of the input array by exploring each choice recursively.

Identify Repeating Operations

• Primary operation: Recursive calls that explore each subset possibility.
• How many times: Each element can be either included or excluded, so the recursion explores 2^n subsets.

How Execution Grows With Input

As the input size grows, the number of subsets doubles for each new element added.

Input Size (n)	Approx. Operations
10	About 1,024 subsets explored
20	About 1,048,576 subsets explored
30	About 1,073,741,824 subsets explored

Pattern observation: The work doubles with each additional element, growing very fast.

Final Time Complexity

Time Complexity: O(n * 2^n)

This means the time grows very fast because we explore all subsets, and each subset can take up to n steps to build.

Common Mistake

[X] Wrong: "Generating subsets is just a simple loop over the array, so it's O(n)."

[OK] Correct: Each element doubles the number of subsets, so the total work grows exponentially, not linearly.

Interview Connect

Understanding this complexity helps you explain why some problems need exponential time and shows your grasp of recursion and combinatorics.

Self-Check

"What if we only wanted subsets of a fixed size k? How would the time complexity change?"

Practice

1. What does the term powerset mean in the context of sets?

easy

A. The set itself without any subsets

B. All possible subsets of a set including the empty set

C. Only the subsets with exactly two elements

D. Subsets that contain only odd numbers

Solution

1. Step 1: Understand the definition of powerset

   The powerset of a set is the collection of all subsets of that set, including the empty set and the set itself.

2. Step 2: Compare options with the definition

   All possible subsets of a set including the empty set correctly describes the powerset as all possible subsets including the empty set. Other options describe only parts or incorrect subsets.

3. Final Answer:

   All possible subsets of a set including the empty set -> Option B

4. Quick Check:

   powerset = all subsets [OK]

Hint: Powerset means every subset, even empty one [OK]

Common Mistakes:

• Thinking powerset excludes empty set
• Confusing powerset with subsets of fixed size
• Assuming powerset is just the original set

2. Which of the following JavaScript function signatures correctly represents a function to generate all subsets of an array arr?

easy

A. function generateSubsets(arr, subsets) { ... }

B. function generateSubsets(arr[]) { ... }

C. function generateSubsets() { ... }

D. function generateSubsets(arr) { ... }

Solution

1. Step 1: Check valid JavaScript function syntax

   function generateSubsets(arr) { ... } uses correct syntax with one parameter named arr. function generateSubsets(arr[]) { ... } uses invalid syntax with arr[]. function generateSubsets() { ... } has no parameters, which is incomplete for this task. function generateSubsets(arr, subsets) { ... } has two parameters which might be valid but is not the standard signature for generating subsets.

2. Step 2: Choose the most appropriate signature

   function generateSubsets(arr) { ... } is the standard and correct way to define a function that takes an array to generate subsets.

3. Final Answer:

   function generateSubsets(arr) { ... } -> Option D

4. Quick Check:

   Correct function syntax = function generateSubsets(arr) { ... } [OK]

Hint: Function parameters must be valid identifiers without brackets [OK]

Common Mistakes:

• Using array syntax in parameter list (arr[])
• Omitting required parameters
• Adding unnecessary parameters without explanation

3. What is the output of the following JavaScript code?

function subsets(nums) {
  let result = [[]];
  for (const num of nums) {
    const newSubsets = [];
    for (const subset of result) {
      newSubsets.push([...subset, num]);
    }
    result.push(...newSubsets);
  }
  return result;
}

console.log(subsets([1, 2]));

medium

A. [[], [1], [2], [1, 2]]

B. [[], [1], [1, 2]]

C. [[1], [2], [1, 2]]

D. [[], [2], [1, 2]]

Solution

1. Step 1: Trace the initial result and loop

   Initially, result = [[]]. For num=1, newSubsets = [[1]], result becomes [[], [1]]. For num=2, newSubsets = [[2], [1, 2]], result becomes [[], [1], [2], [1, 2]].

2. Step 2: Confirm final output

   The function returns [[], [1], [2], [1, 2]] which matches [[], [1], [2], [1, 2]] exactly.

3. Final Answer:

   [[], [1], [2], [1, 2]] -> Option A

4. Quick Check:

   All subsets of [1,2] = [[], [1], [2], [1, 2]] [OK]

Hint: Each new number doubles subsets by adding to existing ones [OK]

Common Mistakes:

• Missing empty subset in output
• Not adding new subsets correctly
• Confusing order of subsets

4. Identify the error in this JavaScript code that tries to generate all subsets of nums:

function getSubsets(nums) {
  let result = [];
  for (let num of nums) {
    let newSubsets = [];
    for (let subset of result) {
      newSubsets.push(subset.concat(num));
    }
    result = result.concat(newSubsets);
  }
  return result;
}

console.log(getSubsets([1, 2]));

medium

A. The initial result should contain the empty subset [[]]

B. Using concat instead of push causes error

C. The inner loop should iterate over nums, not result

D. Missing return statement

Solution

1. Step 1: Check initial value of result

   The code initializes result as an empty array []. It should start with [[]] to include the empty subset, otherwise no subsets are generated.

2. Step 2: Understand impact of initial value

   Without the empty subset, the inner loop never runs on first iteration, so no subsets are created. Adding [[]] fixes this.

3. Final Answer:

   The initial result should contain the empty subset [[]] -> Option A

4. Quick Check:

   Start with [[]] to generate subsets [OK]

Hint: Always start subsets with empty set [[]] [OK]

Common Mistakes:

• Starting with empty array instead of [[]]
• Confusing concat and push usage
• Looping over wrong array

5. Given an array nums = [1, 2, 2], which code modification correctly generates all unique subsets (no duplicates) using the powerset approach?

hard

A. Remove duplicates from nums before generating subsets

B. Use a Set to store subsets as strings to avoid duplicates

C. Sort nums first, then skip adding duplicate subsets during generation

D. Generate all subsets normally without any change

Solution

1. Step 1: Understand the problem with duplicates

   Array [1, 2, 2] has duplicates. Generating subsets normally will create duplicate subsets like [2] twice.

2. Step 2: Apply sorting and skipping duplicates

   Sorting nums makes duplicates adjacent. During subset generation, skip adding subsets that duplicate previous ones to avoid duplicates in result.

3. Final Answer:

   Sort nums first, then skip adding duplicate subsets during generation -> Option C

4. Quick Check:

   Sort and skip duplicates to get unique subsets [OK]

Hint: Sort array and skip duplicates while generating subsets [OK]

Common Mistakes:

• Ignoring duplicates causing repeated subsets
• Removing duplicates from input changes problem
• Using Set of strings can be inefficient or incorrect