cswork / 模板打开 500 路题单

第 20 站 · 回溯

字符串拆分与构造

按切分点回溯 + 回文预处理 O(n · 2^n)

周赛难度分 难度分 1740–难度分 1740· 中位 难度分 1740（1/10 道题有 zerotrac 周赛分）

打开 500 路题单 · 第 20 站 · 10 题
先学
学完去
没有后续站依赖它。
面试频次
1 家公司考过 · 面经出现 1 次Salesforce 1

先做这道

LC 22括号生成中等
卡住再看

维护左右括号计数，在构造阶段剪去非法前缀。

要点

  1. 回溯的每一层决定「下一段切到哪里」，start 走到 n 就得到一种完整的切法。
  2. 先用 O(n²) 的区间 DP 算出每个子串是不是回文，回溯里的判断就是 O(1)。
  3. 复原 IP 地址、单词拆分也是同一个框架，只是「这一段是否合法」的判断不同。

易错点

  • 在回溯里每次都重新用双指针判断回文，重复计算会让常数大很多。
  • 只要求方案数或最少切几刀时，不要枚举，改用 DP。
  • 子串下标是左闭右开还是左闭右闭要统一；s[start:end+1] 和 substring(start, end+1) 很容易差一位。

看动画

一步一步播放这个模式在小例子上的执行过程。可以暂停、单步前进或后退，拖动进度条跳到任意一步。

交互演示 · 逐步观察

回溯 · 子集的决策树

列出 [1, 2, 3] 的所有子集

换个输入
{}
当前处理已发现 / 已计算答案
已收集的子集
空
深度
0
当前路径
{}
结果数
0

从空集出发，先决定是否选 1。

始终成立每层决定一个数选或不选；递归返回时撤销这一步，路径恢复原状，再试另一个分支。

模板

选一种语言展开。四种写法实现的是同一个模板，每一份都编译运行过，并用测试数据核对了输出。看完用它重写热身题 LC 22。

Python
def partition(s: str) -> list[list[str]]:
    """Every way to cut s into palindromes."""
    n = len(s)
    pal = [[False] * n for _ in range(n)]  # pal[i][j]: s[i..j] is a palindrome
    for i in range(n - 1, -1, -1):
        for j in range(i, n):
            pal[i][j] = s[i] == s[j] and (j - i < 2 or pal[i + 1][j - 1])
    res, path = [], []

    def dfs(start: int) -> None:
        if start == n:
            res.append(path[:])
            return
        for end in range(start, n):  # the next piece is s[start..end]
            if pal[start][end]:
                path.append(s[start : end + 1])
                dfs(end + 1)
                path.pop()

    dfs(0)
    return res
C++
// Every way to cut s into palindromes.
vector<vector<string>> partition(const string& s) {
    int n = s.size();
    vector<vector<bool>> pal(n, vector<bool>(n, false));  // pal[i][j]: s[i..j] is a palindrome
    for (int i = n - 1; i >= 0; i--)
        for (int j = i; j < n; j++) pal[i][j] = s[i] == s[j] && (j - i < 2 || pal[i + 1][j - 1]);
    vector<vector<string>> res;
    vector<string> path;
    function<void(int)> dfs = [&](int start) {
        if (start == n) {
            res.push_back(path);
            return;
        }
        for (int end = start; end < n; end++)  // the next piece is s[start..end]
            if (pal[start][end]) {
                path.push_back(s.substr(start, end - start + 1));
                dfs(end + 1);
                path.pop_back();
            }
    };
    dfs(0);
    return res;
}
Java
class Solution {
    private final List<List<String>> res = new ArrayList<>();
    private final List<String> path = new ArrayList<>();
    private boolean[][] pal; // pal[i][j]: s[i..j] is a palindrome
    private String s;

    // Every way to cut s into palindromes.
    List<List<String>> partition(String s) {
        int n = s.length();
        this.s = s;
        pal = new boolean[n][n];
        for (int i = n - 1; i >= 0; i--)
            for (int j = i; j < n; j++)
                pal[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 2 || pal[i + 1][j - 1]);
        res.clear();
        dfs(0);
        return res;
    }

    private void dfs(int start) {
        if (start == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int end = start; end < s.length(); end++) // the next piece is s[start..end]
            if (pal[start][end]) {
                path.add(s.substring(start, end + 1));
                dfs(end + 1);
                path.remove(path.size() - 1);
            }
    }
}
Go
// partition returns every way to cut s into palindromes.
func partition(s string) [][]string {
	n := len(s)
	pal := make([][]bool, n) // pal[i][j]: s[i..j] is a palindrome
	for i := range pal {
		pal[i] = make([]bool, n)
	}
	for i := n - 1; i >= 0; i-- {
		for j := i; j < n; j++ {
			pal[i][j] = s[i] == s[j] && (j-i < 2 || pal[i+1][j-1])
		}
	}
	var res [][]string
	var path []string
	var dfs func(start int)
	dfs = func(start int) {
		if start == n {
			res = append(res, append([]string(nil), path...))
			return
		}
		for end := start; end < n; end++ { // the next piece is s[start..end]
			if pal[start][end] {
				path = append(path, s[start:end+1])
				dfs(end + 1)
				path = path[:len(path)-1]
			}
		}
	}
	dfs(0)
	return res
}

常见变体

这一站的题还会用到下面 2 种写法。展开看什么时候换用它，代码同样四种语言都跑过测试。

按计数约束生成括号时间 O(4^n / √n)（卡特兰数个结果）· 递归深度 O(n)

每一步只有少数几种字符可选、靠计数就能剪枝（括号、IP 段数、字母大小写）：左括号还有剩就能放，右括号只在比左括号少时才能放，这样走到长度 2n 的都是合法串，不用最后再检查。LC 22 括号生成，LC 301 删除无效的括号用同样的计数。

Python
def generate_parentheses(n: int) -> list[str]:
    """Every balanced string of n pairs of parentheses (LC 22)."""
    res, path = [], []

    def dfs(opened: int, closed: int) -> None:
        if len(path) == 2 * n:
            res.append("".join(path))
            return
        if opened < n:  # an opening bracket fits while some are left
            path.append("(")
            dfs(opened + 1, closed)
            path.pop()
        if closed < opened:  # a closing bracket needs an unmatched opening one
            path.append(")")
            dfs(opened, closed + 1)
            path.pop()

    dfs(0, 0)
    return res
C++
// Every balanced string of n pairs of parentheses (LC 22).
vector<string> generateParentheses(int n) {
    vector<string> res;
    string path;
    function<void(int, int)> dfs = [&](int opened, int closed) {
        if ((int)path.size() == 2 * n) {
            res.push_back(path);
            return;
        }
        if (opened < n) {  // an opening bracket fits while some are left
            path.push_back('(');
            dfs(opened + 1, closed);
            path.pop_back();
        }
        if (closed < opened) {  // a closing bracket needs an unmatched opening one
            path.push_back(')');
            dfs(opened, closed + 1);
            path.pop_back();
        }
    };
    dfs(0, 0);
    return res;
}
Java
class Solution {
    private final List<String> res = new ArrayList<>();
    private final StringBuilder path = new StringBuilder();
    private int n;

    // Every balanced string of n pairs of parentheses (LC 22).
    List<String> generateParentheses(int n) {
        this.n = n;
        res.clear();
        dfs(0, 0);
        return new ArrayList<>(res);
    }

    private void dfs(int opened, int closed) {
        if (path.length() == 2 * n) {
            res.add(path.toString());
            return;
        }
        if (opened < n) { // an opening bracket fits while some are left
            path.append('(');
            dfs(opened + 1, closed);
            path.deleteCharAt(path.length() - 1);
        }
        if (closed < opened) { // a closing bracket needs an unmatched opening one
            path.append(')');
            dfs(opened, closed + 1);
            path.deleteCharAt(path.length() - 1);
        }
    }
}
Go
// generateParentheses returns every balanced string of n pairs of parentheses (LC 22).
func generateParentheses(n int) []string {
	var res []string
	path := make([]byte, 0, 2*n)
	var dfs func(opened, closed int)
	dfs = func(opened, closed int) {
		if len(path) == 2*n {
			res = append(res, string(path))
			return
		}
		if opened < n { // an opening bracket fits while some are left
			path = append(path, '(')
			dfs(opened+1, closed)
			path = path[:len(path)-1]
		}
		if closed < opened { // a closing bracket needs an unmatched opening one
			path = append(path, ')')
			dfs(opened, closed+1)
			path = path[:len(path)-1]
		}
	}
	dfs(0, 0)
	return res
}
切分数字串并插入运算符时间 O(n · 4^n) · 递归深度 O(n)

在数字之间放 + - *、问哪些式子等于目标值：每层选下一个数的终点（不能有前导零），三种运算各递归一次。乘法优先级更高，所以要带着「最后一项」last，乘法时先减掉它再加上 last × x。LC 282 给表达式添加运算符。

Python
def add_operators(num: str, target: int) -> list[str]:
    """Every way to put + - * between the digits of num so it equals target (LC 282)."""
    res = []

    def dfs(i: int, expr: str, value: int, last: int) -> None:
        # value: the expression so far; last: its final term, which a * must take back
        if i == len(num):
            if value == target:
                res.append(expr)
            return
        for j in range(i, len(num)):
            if j > i and num[i] == "0":
                break  # no numbers with a leading zero
            s = num[i : j + 1]
            x = int(s)
            if i == 0:
                dfs(j + 1, s, x, x)
            else:
                dfs(j + 1, expr + "+" + s, value + x, x)
                dfs(j + 1, expr + "-" + s, value - x, -x)
                dfs(j + 1, expr + "*" + s, value - last + last * x, last * x)  # * binds tighter

    dfs(0, "", 0, 0)
    return res
C++
// Every way to put + - * between the digits of num so it equals target (LC 282).
vector<string> addOperators(const string& num, long long target) {
    vector<string> res;
    // value: the expression so far; last: its final term, which a * must take back
    function<void(size_t, const string&, long long, long long)> dfs = [&](size_t i, const string& expr, long long value, long long last) {
        if (i == num.size()) {
            if (value == target) res.push_back(expr);
            return;
        }
        for (size_t j = i; j < num.size(); j++) {
            if (j > i && num[i] == '0') break;  // no numbers with a leading zero
            string s = num.substr(i, j - i + 1);
            long long x = stoll(s);
            if (i == 0) {
                dfs(j + 1, s, x, x);
            } else {
                dfs(j + 1, expr + "+" + s, value + x, x);
                dfs(j + 1, expr + "-" + s, value - x, -x);
                dfs(j + 1, expr + "*" + s, value - last + last * x, last * x);  // * binds tighter
            }
        }
    };
    dfs(0, "", 0, 0);
    return res;
}
Java
class Solution {
    private final List<String> res = new ArrayList<>();
    private String num;
    private long target;

    // Every way to put + - * between the digits of num so it equals target (LC 282).
    List<String> addOperators(String num, long target) {
        this.num = num;
        this.target = target;
        res.clear();
        dfs(0, "", 0, 0);
        return new ArrayList<>(res);
    }

    // value: the expression so far; last: its final term, which a * must take back.
    private void dfs(int i, String expr, long value, long last) {
        if (i == num.length()) {
            if (value == target) res.add(expr);
            return;
        }
        for (int j = i; j < num.length(); j++) {
            if (j > i && num.charAt(i) == '0') break; // no numbers with a leading zero
            String s = num.substring(i, j + 1);
            long x = Long.parseLong(s);
            if (i == 0) {
                dfs(j + 1, s, x, x);
            } else {
                dfs(j + 1, expr + "+" + s, value + x, x);
                dfs(j + 1, expr + "-" + s, value - x, -x);
                dfs(j + 1, expr + "*" + s, value - last + last * x, last * x); // * binds tighter
            }
        }
    }
}
Go
import "strconv"

// addOperators returns every way to put + - * between the digits of num so it equals target (LC 282).
func addOperators(num string, target int) []string {
	res := []string{}
	// value: the expression so far; last: its final term, which a * must take back
	var dfs func(i int, expr string, value, last int)
	dfs = func(i int, expr string, value, last int) {
		if i == len(num) {
			if value == target {
				res = append(res, expr)
			}
			return
		}
		for j := i; j < len(num); j++ {
			if j > i && num[i] == '0' {
				break // no numbers with a leading zero
			}
			s := num[i : j+1]
			x, _ := strconv.Atoi(s)
			if i == 0 {
				dfs(j+1, s, x, x)
			} else {
				dfs(j+1, expr+"+"+s, value+x, x)
				dfs(j+1, expr+"-"+s, value-x, -x)
				dfs(j+1, expr+"*"+s, value-last+last*x, last*x) // * binds tighter
			}
		}
	}
	dfs(0, "", 0, 0)
	return res
}

为什么对

  1. 每种切分方式唯一对应一串递增的切点，搜索每层决定「下一段在哪里结束」，所以每种切分恰好生成一次。
  2. 回文表 isPal[i][j] = (s[i] == s[j]) 且 isPal[i+1][j−1]，只依赖更短的区间，所以 i 从后往前填，用到时一定已经算好。
  3. 剪枝只剪「当前这一段不合法」的分支：不合法的段不可能出现在任何合法切分里，剪掉不会漏解。

30 秒口述稿

面试官让你讲思路时，按做法、为什么对、复杂度的顺序说。中英文各一版，可以对着读几遍。

中文
字符串切分我用回溯，每一层决定下一段在哪里结束，start 走到末尾就得到一种完整切分；每种切分对应唯一一串切点，所以不重不漏。判断某一段是否回文，我先用 O(n²) 的区间 DP 预处理，搜索里每次检查就是 O(1)。复原 IP、单词拆分也是同一个框架，只是这一段是否合法的判断不同。答案数最坏是指数级，复杂度 O(n · 2^n)。
English
To partition a string I backtrack, and each level chooses where the next piece ends; when start reaches the end I have one complete split, and since each split is a unique sequence of cuts, none repeats or goes missing. I precompute an O(n²) palindrome table so each check inside the search is O(1). Restoring IP addresses and word break use the same frame with a different validity test. The number of answers can be exponential, so the worst case is O(n · 2^n).

自评一下

对照上面的答案给自己打个分。没掌握的题会按 1、3、7、21 天的间隔回来，到期的题在「我的进度 · 到期复习」里。 只存在这台设备上；登录后会合并到你的账号。

对照要点（0/3）
这道题你会了吗？

小测

3 道概念题和复杂度题。答过的题会和 OA 选择题练习一起按间隔回来复习。 去 OA 选择题练习

3 道题
  1. 回溯生成 n 对括号的所有合法组合时，什么条件下可以追加一个右括号「)」？
  2. 3 对括号能组成多少个合法（配对正确）的括号串？
  3. 回溯枚举字符串 s（长度 n）的所有回文划分时，先预处理一张表 pal[i][j]（s[i..j] 是否为回文），带来的改变是？

作答记录只保存在这台设备的浏览器里；登录后打开OA 选择题练习页，会存进账号。

模板练习

用上面的模板和变体出题：把打乱的行排回原序，把挖掉的边界条件填回去，或者在空白编辑器里整段默写，跑本站的测试并逐行对比。每次「换一题」都会重新出题。

下面几行被打乱了。点一行选中，再点另一行和它交换，排回模板原来的顺序；缩进是提示。

def partition(s: str) -> list[list[str]]:
    """Every way to cut s into palindromes."""
    n = len(s)
    pal = [[False] * n for _ in range(n)]
    for i in range(n - 1, -1, -1):

    dfs(0)
    return res

分档练习

本站在 500 路里的 10 道题，按基础、核心、进阶分三档。每题附一句话思路，先自己想，想不出再看。

核心 5

#题目一句话思路难度分
22括号生成维护左右括号计数，在构造阶段剪去非法前缀。
131分割回文串枚举切割位置并验证回文，构建所有合法分段方案。
93复原 IP 地址按段切分IP地址，处理前导零、长度与数值范围。
320列举单词的全部缩写 🔒把连续省略长度作为状态，在保留字符时统一结算计数。
254因子的组合 🔒以递增因子枚举分解方案，避免因子排列产生重复答案。

进阶 5

#题目一句话思路难度分
267回文排列 II 🔒先验证回文排列的奇偶条件，再枚举一半字符生成唯一结果。
291单词规律 II 🔒回溯建立字符到子串的双向映射，保持一一对应关系。
1593拆分字符串使唯一子字符串的数目最大枚举字符串切分并维护已用子串集合，用剩余长度剪枝。难度分 1740
301删除无效的括号在最少删除约束下生成有效括号字符串，并去除重复答案。
282给表达式添加运算符插入运算符时维护累计值与上一项，正确处理乘法优先级和前导零。

本站 OA 真题 1

全部 1 道