从“逃离一线”到代码实现：深入解析组合问题的DFS解法与剪枝优化

有人把一线城市的房子卖了，手握一千万现金，选择回到五线城市去做生意，图的是生活成本低、节奏更舒适。

网友们对此看法不一，有人羡慕这份“自由”，也有人提醒生意场的水很深，现金看着多，不经烧，行业不熟更是风险重重。

在我看来，这件事的关键或许不在于“逃离”本身有多爽，而在于是否算清了生活、生意和风险这几本账。踏实调研、小步试错、留足备用金，才是让日子真正“滋润”起来的基石。

面试题：组合问题

昨晚十一点多，我在公司楼下抽烟（别学），组里的小李突然微信问我：“东哥，那个‘组合’题你会不会写？我卡死了……”

我正琢磨晚饭到底点没点，他又补了一句：“就是从1到n里挑k个数，所有不重复的搭配都要列出来。”

这听着像数学题，其实是后端开发中的常见需求。比如设计优惠券的“凑单”组合、权限系统的“角色”组合、AB实验的“方案”组合等等。很多业务都需要枚举组合，如果代码写得不够高效，线上服务一跑起来，CPU占用率可能直接起飞。

我告诉他别急，组合问题的核心思路就一句：每次选一个数，往后走，别回头。 一旦回头选择更小的数，就会产生重复组合，例如先选2再选1，就和先选1再选2的结果撞车了。

另一个关键点是剪枝。很多人写回溯不剪枝，当n=20，k=10时，递归层数爆炸，能把电脑跑热。剪枝的逻辑是：假设你还需要选择need个数，从当前位置start开始往后数，剩余的数字数量如果已经不够need个了，那就没有必要继续递归下去，纯属浪费计算资源。

我当场给他写了一个Java版本的实现，风格比较“业务”，方便直接整合到项目里修改：

import java.util.ArrayList;
import java.util.List;

public class Combinations {

    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        if (n <= 0 || k < 0 || k > n) return ans;
        dfs(1, n, k, new ArrayList<>(), ans);
        return ans;
    }

    // start：下一次从哪个数开始选（保证不重复）
    // need：还需要选几个
    private void dfs(int start, int n, int need, List<Integer> path, List<List<Integer>> ans) {
        if (need == 0) {
            ans.add(new ArrayList<>(path)); // 注意要拷贝，不然回溯会把结果改掉
            return;
        }

        // 剪枝：从 i 到 n 一共 (n - i + 1) 个数，必须 >= need 才有意义
        // i 最大只能到 n - need + 1
        for (int i = start; i <= n - need + 1; i++) {
            path.add(i);
            dfs(i + 1, n, need - 1, path, ans);
            path.remove(path.size() - 1);
        }
    }

    // 小测一下
    public static void main(String[] args) {
        Combinations c = new Combinations();
        System.out.println(c.combine(4, 2));
        // 预期：[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]
    }
}

这段代码里有两个最容易踩坑的地方：
一是 ans.add(new ArrayList<>(path)) 这行。很多人图省事直接写 ans.add(path)，结果回溯过程中path列表被修改，之前存入结果集的内容也跟着变了，上演一场“我明明存了，怎么没了”的迷惑现场。
二是for循环的终止条件 i <= n - need + 1。这个剪枝公式是关键，尤其在面试时写出来，能体现出你对算法效率的考虑，面试官通常会对这个细节有好感。

小李接着问：“那如果给的输入不是1到n，而是一个int[] nums数组呢？”
我说原理一样，把循环变量i当作数组下标来处理，start变为下标起始位置，组合时取 nums[i] 的值即可，核心原则依旧是“只往后选”。

另外，如果业务上只需要组合的数量而不需要具体列表，可以用数学中的组合数公式直接计算。但线上业务通常需要枚举出所有具体方案进行后续处理，所以老老实实用回溯算法往往是最稳妥的选择。

说到这，我想起上周的一个需求：产品经理希望对一个功能开关的所有可能组合进行灰度测试。这个“所有组合”的要求让我差点当场沉默，组合爆炸的威力可不是闹着玩的。在实际开发中，一定要有意识地剪枝、限制问题规模，别让不合理的需求把系统拖垮。

技术问题的解决，往往需要在理解原理的基础上，写出既正确又高效的代码。如果你对这类算法实现或后端开发中的实际应用有更多想法，欢迎在云栈社区与其他开发者一起交流探讨。