78. Subsets

At a Glance

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

Problem (one-liner)

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.

Recognition Cues

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

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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;
}