京公网安备11010502063487号给定一个元素互不相同的数组，返回它的所有子集（幂集），包括空集和它本身，顺序不限。n 个元素有 2^n 个子集，因为每个元素"选"或"不选"。这道题有三种常见做法：回溯（每个结点都是一个子集）、位掩码（用 0 到 2^n - 1 的每个整数的二进制位表示选哪些元素）、逐个翻倍（每来一个新元素，把已有的所有子集各复制一份并加上它）。本文在 Python 里实现了这三种，用真实数据验证它们结果一致并比较耗时，给出五种语言的回溯实现，并把回溯过程做成分步演示。
完整题目见官方页面（链接在文末）。结果按集合比较（每个子集内部排序，子集之间也排序）。基准解是标准库的 itertools.combinations：对每个长度 r 从 0 到 n，列出所有选 r 个的组合，与回溯是两种独立的写法。一共 10 组用例，覆盖：官方示例、空数组、单个元素、含负数、长度 4 到 6：
输入 [[1,2,3]] 输出 [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]] 输入 [[0]] 输出 [[],[0]] 输入 [[]] 输出 [[]] 输入 [[1,2]] 输出 [[],[1],[2],[1,2]] 输入 [[5,-5]] 输出 [[],[5],[-5],[5,-5]] 输入 [[1,2,3,4]] 输出 [[],[1],[2],[3],[4],[1,2],[1,3],[1,4],[2,3],[2,4],[3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4],[1,2,3,4]]
与"组合"（第 77 题）不同的是，这里不需要等到路径满了才收集：走到任何一个结点，当前路径 path 本身就是一个合法的子集。所以每次进入 dfs 就先收集一份 path 的副本，再从 start 起依次尝试加入后面的每个元素，递归，撤销。start 保证元素只往后选，同一个子集不会被排成不同顺序。Python、Java、Go、JavaScript、C++ 都是真实编译运行的。
Python · 解法代码def solve(nums): res, path = [], [] def dfs(start): res.append(path[:]) # 每个结点（每一条路径）本身就是一个子集，不用等到最后 for i in range(start, len(nums)): path.append(nums[i]) dfs(i + 1) # 只往后选，保证同一个子集不会被排列成多种顺序 path.pop() dfs(0) return res
$ python3 solution.py # 统一入口：逐行读取 cases.jsonl，调用上面的 solve，打印 JSON [[1,2,3]] → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] [[0]] → [[],[0]] [[]] → [[]] [[1,2]] → [[],[1],[1,2],[2]] [[5,-5]] → [[],[5],[5,-5],[-5]] [[1,2,3,4]] → [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]
Java · 解法代码class Solution { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); dfs(nums, 0, new ArrayList<>(), res); return res; } private void dfs(int[] nums, int start, List<Integer> path, List<List<Integer>> res) { res.add(new ArrayList<>(path)); // 每个结点（每一条路径）本身就是一个子集，不用等到最后 for (int i = start; i < nums.length; i++) { path.add(nums[i]); dfs(nums, i + 1, path, res); // 只往后选，保证同一个子集不会被排列成多种顺序 path.remove(path.size() - 1); } } }
$ javac -d build Main.java Solution.java && java -cp build Main < cases.jsonl [[1,2,3]] → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] [[0]] → [[],[0]] [[]] → [[]] [[1,2]] → [[],[1],[1,2],[2]] [[5,-5]] → [[],[5],[5,-5],[-5]] [[1,2,3,4]] → [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]
Go · 解法代码func subsets(nums []int) [][]int { res := [][]int{} path := []int{} var dfs func(start int) dfs = func(start int) { res = append(res, append([]int{}, path...)) // 每个结点（每一条路径）本身就是一个子集，不用等到最后 for i := start; i < len(nums); i++ { path = append(path, nums[i]) dfs(i + 1) // 只往后选，保证同一个子集不会被排列成多种顺序 path = path[:len(path)-1] } } dfs(0) return res }
$ go build -o bin . && ./bin < cases.jsonl [[1,2,3]] → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] [[0]] → [[],[0]] [[]] → [[]] [[1,2]] → [[],[1],[1,2],[2]] [[5,-5]] → [[],[5],[5,-5],[-5]] [[1,2,3,4]] → [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]
JavaScript · 解法代码function subsets(nums) { const res = []; const path = []; const dfs = (start) => { res.push([...path]); // 每个结点（每一条路径）本身就是一个子集，不用等到最后 for (let i = start; i < nums.length; i++) { path.push(nums[i]); dfs(i + 1); // 只往后选，保证同一个子集不会被排列成多种顺序 path.pop(); } }; dfs(0); return res; }
$ node run.js < cases.jsonl [[1,2,3]] → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] [[0]] → [[],[0]] [[]] → [[]] [[1,2]] → [[],[1],[1,2],[2]] [[5,-5]] → [[],[5],[5,-5],[-5]] [[1,2,3,4]] → [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]
C++ · 解法代码#include <vector> using namespace std; class Solution { void dfs(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& res) { res.push_back(path); // 每个结点（每一条路径）本身就是一个子集，不用等到最后 for (int i = start; i < (int)nums.size(); i++) { path.push_back(nums[i]); dfs(nums, i + 1, path, res); // 只往后选，保证同一个子集不会被排列成多种顺序 path.pop_back(); } } public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; vector<int> path; dfs(nums, 0, path, res); return res; } };
$ clang++ -std=c++17 -O2 -o bin sol.cpp && ./bin < cases.jsonl [[1,2,3]] → [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]] [[0]] → [[],[0]] [[]] → [[]] [[1,2]] → [[],[1],[1,2],[2]] [[5,-5]] → [[],[5],[5,-5],[-5]] [[1,2,3,4]] → [[],[1],[1,2],[1,2,3],[1,2,3,4],[1,2,4],[1,3],[1,3,4],[1,4],[2],[2,3],[2,3,4],[2,4],[3],[3,4],[4]]
共 10 组用例（含边界），以暴力解的结果为基准逐组比对： Python 通过 10/10 Java 通过 10/10 Go 通过 10/10 JavaScript 通过 10/10 C++ 通过 10/10
我在 Python 里实现了另外两种做法：位掩码（对每个整数 0 到 2^n - 1，二进制里为 1 的位对应选中的元素）和逐个翻倍。对 n 从 10 到 18 都数出了结果个数是否等于 2^n，n ≤ 14 时还用集合比较了三种做法的结果完全一致，并测了耗时（每个取三次中最快的一次）：
三种做法的结果个数（是否都等于 2^n）和耗时（各取三次中最快）： n=10: 2^n = 1024；回溯 0.15 ms（1024 个） 位掩码 0.46 ms（1024 个） 逐个翻倍 0.07 ms（1024 个） 结果一致：True n=14: 2^n = 16384；回溯 2.96 ms（16384 个） 位掩码 10.28 ms（16384 个） 逐个翻倍 1.64 ms（16384 个） 结果一致：True n=16: 2^n = 65536；回溯 13.45 ms（65536 个） 位掩码 46.33 ms（65536 个） 逐个翻倍 8.30 ms（65536 个） 结果一致：未比较 n=18: 2^n = 262144；回溯 64.19 ms（262144 个） 位掩码 231.66 ms（262144 个） 逐个翻倍 57.70 ms（262144 个） 结果一致：未比较
三种做法生成的子集个数都等于 2^n（n = 18 时是 262144 个）。耗时上，逐个翻倍最快（n = 18 时 57.7ms），回溯次之（64.2ms），位掩码最慢（231.7ms），约是回溯的 3.6 倍：位掩码要对每个整数检查 n 个二进制位，总共 n × 2^n 次判断，而回溯和翻倍每生成一个子集只做与它大小成正比的工作。这只是 Python 里的实测，n = 16 和 18 时没有再做结果集合的比较（数量太大），但个数是对的。
Python 版本另外和 itertools.combinations 做了随机对拍，长度 0 到 8、元素互不相同：
随机对拍 2000 组（长度 0 到 8、互不相同的整数；结果按集合比较），solve 与 brute 的结果全部一致。
另外四种语言只在上面 10 组固定用例上验证过，没有做大规模随机对拍。这道题的输出就有 2^n 个子集，耗时完全由输出规模决定，所以没有另做规模对比实验，上一节的表就是主要的耗时数据。
下面的演示用 [1, 2, 3]。深度优先地走：空集 → [1] → [1, 2] → [1, 2, 3]，回退后 [1, 3]，再回退到 [2] → [2, 3]，最后 [3]。共 8 个（2³）。每一帧都是把上面的解法在这组输入上真实执行记录下来的，运行器还检查了演示最终得到的子集集合与 solve 的返回值一致。