Frontend School

Generate Subsets

DSA
easy

Generate Subsets

Easy
Backtracking
Arrays
Subset

Overview

In software development, efficiently enumerating all possible combinations or configurations is a fundamental task. This problem challenges you to generate every possible subset of a given set of numbers, which is a core skill for tackling combinatorial optimization and decision-making algorithms.

What you need to do / Task

Implement a function subsets that takes an array of unique integers nums and returns a list containing all possible subsets (also known as the power set). The order of subsets in the output list, and the order of elements within each subset, does not matter.

Input & output

  • Input: nums: number[]
    • An array of unique integers.
  • Output: number[][]
    • A 2D array (list of lists) of integers, where each inner array represents a unique subset of the input nums.

Clarifications

  • The order of subsets in the final output does not matter.
  • The order of elements within each subset does not matter. For example, [1,2] is considered the same subset as [2,1].

Examples

1

Example 1

Input:

nums = [1,2,3]

Output:

[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

Note:

These are all 2^3 = 8 possible subsets. The order of subsets and elements within subsets might vary but the content must be the same.

2

Example 2

Input:

nums = [0]

Output:

[[],[0]]

Note:

For a single element array, there are 2^1 = 2 subsets: the empty set and the set containing the element itself.

3

Example 3

Input:

nums = [1,2]

Output:

[[],[1],[2],[1,2]]

Note:

For two elements, there are 2^2 = 4 subsets.

Constraints

Constraints & assumptions

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • All elements in nums are unique.

What interviewers evaluate

  • Ability to design and implement a correct backtracking algorithm.
  • Proper management of recursive state and base cases.
  • Correctly generating all unique subsets without omissions or duplicates.
  • Communicating the time and space complexity of the solution.

Loading editor...