昨天晚上十一点多吧，我在公司楼下抽烟…那个风特别冷，你们懂的，然后我们组小李跑下来问我：东哥，子集这题我怎么写都写乱了，一会儿漏，一会儿重复。说真的，这题看着像“背模板”，但你真上生产写权限系统、写灰度开关、写策略组合的时候，它就是子集，换个马甲而已。
比如你们做个“功能开关”，A/B/C 三个开关，产品说要把所有组合都跑一遍回归，那不就是把 [A,B,C] 的所有子集列出来嘛。然后你脑子里就得有个画面：每个元素只有两种命运——进集合，或者不进集合。嗯，就这么朴素，别把它想成啥高深算发…算法。
我当时就跟小李说，你别急着敲代码，你先把“走路路线”想明白：你走到第 i 个数，你要么拿它，要么不拿它；走到尽头，就把手里这包“已选的”记一笔。这个过程用回溯最顺手，写起来也不容易丢。
代码我当场在会议室白板旁边敲的（键盘还黏黏的，估计是下午奶茶洒了…离谱），大概长这样：
import java.util.*;publicclassSubsets{publicstatic List<List<Integer>> subsets(int[] nums) { List<List<Integer>> ans = new ArrayList<>(); Deque<Integer> path = new ArrayDeque<>(); dfs(nums, 0, path, ans);return ans; }privatestaticvoiddfs(int[] nums, int idx, Deque<Integer> path, List<List<Integer>> ans){// 走到这里就算一种组合，先收下 ans.add(new ArrayList<>(path));// 从 idx 往后选，保证不回头，就不会重复for (int i = idx; i < nums.length; i++) { path.addLast(nums[i]); dfs(nums, i + 1, path, ans); path.removeLast(); // 撤销选择，继续试别的路 } }publicstaticvoidmain(String[] args){int[] nums = {1, 2, 3}; System.out.println(subsets(nums)); }}
你看这个写法有个很“工程”的味道：ans.add(new ArrayList<>(path)) 这行位置很关键，放在 for 前面意味着“任何时刻的 path 都是一种合法子集”，包括空集。很多人漏空集就是漏在这儿，或者把收集结果写到递归出口，结果路径没走全，手一抖就少一半。
然后小李又问我：那复杂度咋算，我面试老被追着问。我说你就别装了…这题本来就得生成 2^n 个结果，你再怎么优化也得写出来吧，所以时间大概是 O(n * 2^n)（每个子集复制一次，平均长度跟 n 有关），空间除了答案以外，递归深度 O(n)。面试官要是继续追，你就把“输出规模”这个词甩过去，基本就能停火。
当然你要是更喜欢“位运算那套”，也行，像你在配置中心做开关组合，有时候用 bitmask 特别直观：0 到 2^n - 1，哪一位是 1 就选哪个元素。写法也给你一份，短平快，适合写工具脚本那种：
import java.util.*;publicclassSubsetsBitmask{publicstatic List<List<Integer>> subsets(int[] nums) {int n = nums.length; List<List<Integer>> ans = new ArrayList<>();int total = 1 << n;for (int mask = 0; mask < total; mask++) { List<Integer> cur = new ArrayList<>();for (int i = 0; i < n; i++) {if (((mask >> i) & 1) == 1) cur.add(nums[i]); } ans.add(cur); }return ans; }}
我一般会跟新人说一句“别死背写法”，你把它当成你在排查线上事故时的分叉路口就行：每个开关、每个条件，都是选/不选。回溯就是你一条路走到黑再回头，bitmask 就是你一次把所有路编号跑一遍，各有各的舒服。
哦对了，临走小李还补了一嘴：要是数组里有重复数字咋办。我说那就是另一个坑了，得先排序，然后同层去重，不然你会看到重复子集一堆…不过算了我先上楼了，电梯口又卡人了，今天这破楼不知道咋回事。
