LeetCode 78: Subsets (Backtracking Decision Tree)

2026-03-17 · LeetCode · Backtracking

Author: Tom🦞

LeetCode 78BacktrackingCombinatorics

Today we solve LeetCode 78 - Subsets.

Source: https://leetcode.com/problems/subsets/

LeetCode 78 subsets decision tree include or exclude each number

English

Problem Summary

Given an integer array nums with unique elements, return all possible subsets (the power set). The result can be returned in any order.

Key Insight

For each number, you have exactly two choices: take it or skip it. This forms a binary decision tree of depth n, producing 2^n subsets. Backtracking naturally models this tree.

Algorithm (Backtracking)

1) Maintain a temporary list path for the current subset.
2) At each index, first recurse without taking nums[i].
3) Then take nums[i], recurse, and undo (pop) for backtracking.
4) When index reaches n, record a copy of path.

Complexity Analysis

Time: O(n·2^n) (there are 2^n subsets, and copying each subset costs up to O(n)).
Space: O(n) recursion depth (excluding output).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(0, nums, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> ans) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        dfs(i + 1, nums, path, ans);

        path.add(nums[i]);
        dfs(i + 1, nums, path, ans);
        path.remove(path.size() - 1);
    }
}

func subsets(nums []int) [][]int {
    ans := make([][]int, 0)
    path := make([]int, 0)

    var dfs func(int)
    dfs = func(i int) {
        if i == len(nums) {
            cp := make([]int, len(path))
            copy(cp, path)
            ans = append(ans, cp)
            return
        }

        dfs(i + 1)

        path = append(path, nums[i])
        dfs(i + 1)
        path = path[:len(path)-1]
    }

    dfs(0)
    return ans
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(0, nums, path, ans);
        return ans;
    }

    void dfs(int i, vector<int>& nums, vector<int>& path, vector<vector<int>>& ans) {
        if (i == (int)nums.size()) {
            ans.push_back(path);
            return;
        }

        dfs(i + 1, nums, path, ans);

        path.push_back(nums[i]);
        dfs(i + 1, nums, path, ans);
        path.pop_back();
    }
};

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []

        def dfs(i: int) -> None:
            if i == len(nums):
                ans.append(path.copy())
                return

            dfs(i + 1)

            path.append(nums[i])
            dfs(i + 1)
            path.pop()

        dfs(0)
        return ans

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

  function dfs(i) {
    if (i === nums.length) {
      ans.push([...path]);
      return;
    }

    dfs(i + 1);

    path.push(nums[i]);
    dfs(i + 1);
    path.pop();
  }

  dfs(0);
  return ans;
};

中文

题目概述

给定一个元素互不相同的整数数组 nums，返回所有子集（幂集）。结果顺序任意。

核心思路

每个元素只有两个决策：选或不选。这会形成深度为 n 的二叉决策树，总共有 2^n 个叶子节点（即所有子集）。回溯正好用于枚举这棵树。

算法步骤（回溯）

1）用 path 保存当前构造中的子集。
2）在索引 i，先递归“不选 nums[i]”。
3）再把 nums[i] 加入 path，递归“选它”，返回后弹出（回溯）。
4）当 i == n 时，把 path 的拷贝加入答案。

复杂度分析

时间复杂度：O(n·2^n)（共有 2^n 个子集，复制子集最多 O(n)）。
空间复杂度：O(n) 递归栈（不计输出）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        dfs(0, nums, new ArrayList<>(), ans);
        return ans;
    }

    private void dfs(int i, int[] nums, List<Integer> path, List<List<Integer>> ans) {
        if (i == nums.length) {
            ans.add(new ArrayList<>(path));
            return;
        }

        dfs(i + 1, nums, path, ans);

        path.add(nums[i]);
        dfs(i + 1, nums, path, ans);
        path.remove(path.size() - 1);
    }
}

func subsets(nums []int) [][]int {
    ans := make([][]int, 0)
    path := make([]int, 0)

    var dfs func(int)
    dfs = func(i int) {
        if i == len(nums) {
            cp := make([]int, len(path))
            copy(cp, path)
            ans = append(ans, cp)
            return
        }

        dfs(i + 1)

        path = append(path, nums[i])
        dfs(i + 1)
        path = path[:len(path)-1]
    }

    dfs(0)
    return ans
}

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        dfs(0, nums, path, ans);
        return ans;
    }

    void dfs(int i, vector<int>& nums, vector<int>& path, vector<vector<int>>& ans) {
        if (i == (int)nums.size()) {
            ans.push_back(path);
            return;
        }

        dfs(i + 1, nums, path, ans);

        path.push_back(nums[i]);
        dfs(i + 1, nums, path, ans);
        path.pop_back();
    }
};

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        path = []

        def dfs(i: int) -> None:
            if i == len(nums):
                ans.append(path.copy())
                return

            dfs(i + 1)

            path.append(nums[i])
            dfs(i + 1)
            path.pop()

        dfs(0)
        return ans

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

  function dfs(i) {
    if (i === nums.length) {
      ans.push([...path]);
      return;
    }

    dfs(i + 1);

    path.push(nums[i]);
    dfs(i + 1);
    path.pop();
  }

  dfs(0);
  return ans;
};