Generate Subsets

Google Interview Question

Poll of the Day

---

Problem Overview

Difficulty: Medium
LeetCode Pattern: Backtracking

Given an integer array nums, return all possible subsets (the power set).

Input:
· nums = [1]
Output:
· [[], [1]]

Input:
· nums = [1,2]
Output:
· [[], [1], [2], [1,2]]

---

Video Solution

---

Step 1: Clarify Requirements

• Can input array be empty?

  • Yes. Return [[]].

• Can input array contain duplicates?

  • No. All elements are unique.

• Does order of the output matter?

  • No. Any order is fine.

---

Step 2: Discuss Approaches

Approach 1: Try All Window Sizes

• Logic:

  • Loop k from 0 to n

  • For each k:

    • Generate all k-length subsets

  • Add them to result

• Big O:

  • Time Complexity: O(n·2ⁿ)

  • Space Complexity: O(n·2ⁿ)

Approach 2: Use Backtracking (Optimal)

• Logic:

  • Recursively explore both paths:

    • include path

    • exclude path

  • Add each path to result

• Big O:

  • Time Complexity: O(n·2ⁿ)

  • Space Complexity: O(n)

---

Step 3: Write Code (Optimal)

Python

---

Java

---

C++

---

Step 4: Answer Follow-Ups

• What if input has duplicates?

  • Use a set to skip duplicates.

• What if subsets need to be in lex order?

  • Sort input, then generate subsets.

• What if we want subsets of size k?

  • Add to result only when:

    • len(path) == k

---

👨‍💻 Need Interview Practice?

• Book a 1:1 with me

• Book Here: Booking URL