78. Subsets

Quick Identifier

Topic: backtracking
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Meta, Google, Microsoft, Bloomberg
Frequency: Very High
LeetCode: 78

Quick Sights

Time Complexity: O(number of states * cost per state); output-heavy problems are bounded by the number of generated states.
Space Complexity: O(recursion depth) excluding the final output unless stated.
Core Mechanism: Given distinct integers nums, return the power set: all 2^n subsets (including empty and full set). Order of subsets or elements may vary unless constrained.

Concept Explanation

Given distinct integers nums, return the power set: all 2^n subsets (including empty and full set). Order of subsets or elements may vary unless constrained.

State the invariant before coding: what partial result is already correct, what work remains, and what value or state each recursive/iterative step must preserve.

Recognition cues:

All subsets / power set
Input values distinct
Classic inclusion/exclusion at each index

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Iterative — bit mask 0..2^n-1 — O(n * 2^n) time.
Optimal — DFS backtrack choose/skip each index — same complexity, cleaner recursion tree.

Optimal Solution

Go

func subsets(nums []int) [][]int {
	result := [][]int{}
	path := make([]int, 0, len(nums))

	var dfs func(start int)
	dfs = func(start int) {
		copied := make([]int, len(path))
		copy(copied, path)
		result = append(result, copied)
		for index := start; index < len(nums); index++ {
			path = append(path, nums[index])
			dfs(index + 1)
			path = path[:len(path)-1]
		}
	}
	dfs(0)
	return result
}

JavaScript

function subsets(nums) {
  const result = [];
  const path = [];

  function dfs(startIndex) {
    result.push([...path]);
    for (let index = startIndex; index < nums.length; index += 1) {
      path.push(nums[index]);
      dfs(index + 1);
      path.pop();
    }
  }

  dfs(0);
  return result;
}