回溯模板实战：组合与切割

上一篇给出了回溯的通用骨架：路径、选择列表、结束条件三要素。这篇用三道经典题把模板逐行讲透——你会发现它们共用同一个模板，差异只在「终止条件 + 收集时机 + 下一层起点」三个插槽上。

组合问题（77）：为什么要 startIndex

77. 组合：给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

如果不需要 startIndex，代码会怎么写？for 从 1 开始无脑遍历：

k=2, n=4 时会同时产出 [1,2] 和 [2,1]

这就是重复组合的来源。组合是无序的，[1,2] 和 [2,1] 是同一个答案。startIndex 的作用就是给"下一层的选择"画一条起跑线：本层选了 i，下层只能从 i+1 开始选，强制序列递增，天然保证每个组合只被枚举一次。

带剪枝的完整代码：

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();
 
    public List<List<Integer>> combine(int n, int k) {
        backtracking(n, k, 1);
        return result;
    }
 
    private void backtracking(int n, int k, int startIndex) {
        // 终止条件：攒够 k 个元素，收集并返回
        if (path.size() == k) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 剪枝：i 的上界是 n-(k-path.size())+1
        for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
            path.addLast(i);             // 做选择
            backtracking(n, k, i + 1);   // 下一层从 i+1 开始
            path.removeLast();           // 撤销选择
        }
    }
}

剪枝公式怎么来的

n - (k - path.size()) + 1 不是背下来的魔法数字，是倒推出来的。已选 path.size() 个，还差 k - path.size() 个；当前从 i 开始，区间 [i, n] 里剩 n - i + 1 个候选，要够用就必须满足：

n - i + 1 >= k - path.size()
→ i <= n - (k - path.size()) + 1

举实例验证：n=4, k=3，path 为空时 i 最大取 4-3+1=2——从 3 开始凑不满 3 个数，剪掉是正确的；当 path 已有 2 个时，i 最大取 4，每个候选都可能成为最后一个元素，边界不误杀。

组合总和（39）：元素可重复选取

39. 组合总和：candidates 数组（元素无重复）中选出和为 target 的组合，每个元素可以被无限次选取。

和 77 相比，唯一的改动在递归参数上：因为同一个元素还能再选，所以下一层的起点仍然是 i（而不是 i+1）。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    Deque<Integer> path = new ArrayDeque<>();
    int sum = 0; // path 中元素之和
 
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); // 排序后可用 sum+candidates[i]>target 提前剪枝
        backtracking(candidates, target, 0);
        return result;
    }
 
    private void backtracking(int[] candidates, int target, int startIndex) {
        // 终止条件一：恰好凑出 target
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        // 终止条件二：超出 target，直接放弃（配合排序剪枝其实到不了这）
        for (int i = startIndex; i < candidates.length; i++) {
            // 剪枝：排序后后面的只会更大，直接 break 而不是 continue
            if (sum + candidates[i] > target) break;
            sum += candidates[i];
            path.addLast(candidates[i]);
            // 关键差异：传 i 不传 i+1，允许重复选当前元素
            backtracking(candidates, target, i);
            sum -= candidates[i];
            path.removeLast();
        }
    }
}

对比记忆：

场景	下一层起点	语义
元素不可重复选（77、216）	`i + 1`	当前元素已消费
元素可重复选（39）	`i`	当前元素可再消费
集合间组合（17 电话号码）	不需要	每层换一个集合，层内遍历即可

一个小思考：39 允许重复选却不会产生 [2,3]/[3,2] 重复，正是因为起点是 i 不是 0——startIndex 依然是防重复的那道闸门，只是闸门位置松了一格。

切割问题（131）：切割线视角

131. 分割回文串：把字符串 s 分割成若干子串，使每个子串都是回文串，返回所有分割方案。

这道题初见很难联想到组合，因为"选择的对象"不是数组里的元素，而是切割线放在哪。转换视角：

s = "aab"
 
a | a | b     ← 两条切割线，三段都回文 ✓
a | ab        ← "ab" 不是回文 ✗
aa | b        ← 两段都回文 ✓
aab           ← "aab" 不是回文 ✗

把切割线抽象成"选择"之后，搜索树就画出来了：树的第一层是在 s[0..1]、s[0..2]… 中选第一个子串，选完之后剩下的部分继续切。startIndex 的语义从"本层从哪个元素开始选"变成了"从哪个位置开始切"：

class Solution {
    List<List<String>> result = new ArrayList<>();
    Deque<String> path = new ArrayDeque<>();
 
    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return result;
    }
 
    private void backtracking(String s, int startIndex) {
        // 终止条件：切割位置到达串尾，说明整套切割线合法
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        // for 遍历的是「切割线的落点」：本段子串是 s[startIndex..i]
        for (int i = startIndex; i < s.length(); i++) {
            if (!isPalindrome(s, startIndex, i)) continue; // 本段非回文，剪掉
            path.addLast(s.substring(startIndex, i + 1)); // 做选择：切一刀
            backtracking(s, i + 1);                       // 从切口的下一格继续
            path.removeLast();                            // 撤销：把刀收回来
        }
    }
 
    // 双指针判断回文
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left++) != s.charAt(right--)) return false;
        }
        return true;
    }
}

注意终止条件变成了 startIndex >= s.length()——组合问题攒够 k 个收，切割问题切到串尾收。另外用动态规划预处理回文表可以把判断降到 O(1)，属于锦上添花的优化，面试时口头提一句即可。

三题模板对齐表

把三个插槽的差异摆在一起，模板感立刻清晰：

要素	77 组合	39 组合总和	131 分割回文串
选择对象	数字 i	数字 candidates[i]	切割线位置 i
终止条件	path.size() == k	sum == target	startIndex 越过串尾
收集时机	只在叶子收	只在叶子收	只在叶子收
下一层起点	i + 1	i（可重复选）	i + 1（切口下一格）
额外剪枝	n-(k-size)+1	排序 + sum 超界 break	非回文子串剪掉

复杂度

77 组合：时间 O(k × C(n,k))，C(n,k) 个解 × 每个解拷贝 O(k)；空间 O(k)（递归深度 + path，不计结果集）。
39 组合总和：时间上界 O(n × 2^target)（树深受 target 限制）；空间 O(target)。
131 分割回文串：时间 O(n × 2^n)（n-1 个切位各有切/不切两种状态 × 拷贝开销）；空间 O(n)。

易错点

忘记拷贝 path：result.add(path) 存的是引用，最终结果全为空列表，这是回溯题第一大坑；
39 误传 i+1：会漏掉元素重复选的合法解（如 [2,2,3]）；
131 的子串区间：本段是 [startIndex, i] 双闭区间，所以 substring 用 i + 1，下一层起点也是 i + 1，三处下标对不上就全盘错位；
剪枝用 continue 还是 break：排序后超界用 break（后面的更大）；非回文子串用 continue（后面的子串还可能回文）。

LeetCode 题目清单

77. 组合：startIndex 的引入场景，剪枝公式的推导原型。
216. 组合总和 III：固定选 9 个数中 k 个、和为 n，组合剪枝 + 和剪枝双重使用。
17. 电话号码的字母组合：多个独立集合求组合，不需要 startIndex，for 遍历当前集合的映射字母。
39. 组合总和：元素可重复选，递归传 i 而非 i+1。
40. 组合总和 II：数组含重复元素，排序后做树层去重（下一篇细讲）。
131. 分割回文串：切割线视角的奠基题。
93. 复原 IP 地址：固定切 4 段，每段 0~255 且无前导零，切问题的变形。

参考

代码随想录 · 回溯算法专题