跳槽去了某大厂，工资从18k涨到32k，每天早会站会周会复盘会，真正写代码的时间不到4小时，PPT做的比代码还多

昨天晚上十一点多吧，我在公司楼下抽烟…那个风特别冷，你们懂的，然后我们组小李跑下来问我：东哥，子集这题我怎么写都写乱了，一会儿漏，一会儿重复。说真的，这题看着像“背模板”，但你真上生产写权限系统、写灰度开关、写策略组合的时候，它就是子集，换个马甲而已。

比如你们做个“功能开关”，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 就是你一次把所有路编号跑一遍，各有各的舒服。

哦对了，临走小李还补了一嘴：要是数组里有重复数字咋办。我说那就是另一个坑了，得先排序，然后同层去重，不然你会看到重复子集一堆…不过算了我先上楼了，电梯口又卡人了，今天这破楼不知道咋回事。