组合与剪枝问题

组合总和问题如何控制元素重复选取？

• 目标: 从候选数组中选出和为 target 的组合;
• 可重复选取: 下一层从 i 开始遍历, 允许同一元素被再次选中;
• 不可重复选取: 下一层从 i + 1 开始遍历;
• 剪枝: 排序后当 sum + nums[i] > target 直接 break, 因为后面的元素只会更大;
• 去重: 同一层中 i > index && nums[i - 1] === nums[i] 时跳过, 避免生成重复组合;

const combinationSum = (candidates, target) => {
  candidates.sort((a, b) => a - b);
  const res = [];
  const backtrack = (state, index, sum) => {
    if (sum === target) {
      res.push([...state]);
      return;
    }
    for (let i = index; i < candidates.length; i++) {
      if (sum + candidates[i] > target) break; // 剪枝
      state.push(candidates[i]);
      backtrack(state, i, sum + candidates[i]); // 传 i 允许重复选取
      state.pop();
    }
  };
  backtrack([], 0, 0);
  return res;
};

• 复杂度: 时间 $O(n \cdot 2^n)$, 空间 $O(n)$;
• 变体: 每个元素至多用一次时把递归参数改成 i + 1, 并加上同层去重判断;

括号生成如何剪枝？

• 状态: tag 表示当前尚未闭合的左括号数量;
• 决策: 添加 ( 时 tag + 1, 添加 ) 时 tag - 1;
• 剪枝: 只有 tag < n 才能加 (, 只有 tag > 0 才能加 );
• 终止: 路径长度达到 $2n$ 且 tag === 0 时记录结果;
• 有效性来源: 两条剪枝保证任意前缀中左括号不少于右括号, 且总数不超限;

const generateParenthesis = (n) => {
  const res = [];
  const backtrack = (state, tag) => {
    if (state.length === 2 * n) {
      if (tag === 0) res.push(state.join(""));
      return;
    }
    if (tag > 0) {
      state.push(")");
      backtrack(state, tag - 1);
      state.pop();
    }
    if (tag < n) {
      state.push("(");
      backtrack(state, tag + 1);
      state.pop();
    }
  };
  backtrack([], 0);
  return res;
};

• 复杂度: 时间与第 $n$ 个卡特兰数同阶 $\frac{2^{2n}}{\sqrt{n}}$, 空间 $O(n)$;

复原 IP 地址如何剪枝？

• 决策: 在字符串中插入 3 个点, 把串切成 4 段;
• 剪枝: 段值大于 255 时 break; 段有前导 0 但不止一位时 break;
• 终止: 切到字符串末尾且恰好 4 段时记录结果;
• 剪枝有效性: 因为 break 而非 continue, 依赖候选段随长度单调不减这一性质;

const restoreIpAddresses = (s) => {
  const res = [];
  const dfs = (state, index) => {
    if (index >= s.length) {
      if (state.length === 4) res.push(state.join("."));
      return;
    }
    for (let i = index; i < s.length; i++) {
      const sub = s.slice(index, i + 1);
      if (sub[0] === "0" && i !== index) break; // 前导 0
      if (Number(sub) > 255) break;
      state.push(sub);
      dfs(state, i + 1);
      state.pop();
    }
  };
  dfs([], 0);
  return res;
};

• 复杂度: 时间 $O(3^4 \cdot |s|)$, 空间 $O(|s|)$;

三类组合剪枝的判据如何归纳？

问题	剪枝判据	终止判据
组合总和	sum + nums[i] > target	sum === target
括号生成	tag > 0 / tag < n	长度 $2n$ 且 tag = 0
复原 IP	段值超 255 / 前导 0	到串尾且 4 段

• 共性: 剪枝都是"当前选择一旦越界, 该分支及其后续选择必然无效";
• 区别: 组合总和与复原 IP 用排序或单调性提前 break, 括号生成用计数值约束;