枚举算法

枚举算法解决什么问题？

• 枚举: 逐个列举解空间中的候选解, 再检查每个候选是否满足条件;
• 别名: 穷举法;
• 代价: 解空间多大就检查多少次, 通常是指数级或多项式级;
• 适用: 规模小、解空间有限且容易判定候选是否合法的问题;

如何缩小枚举范围？

• 约束先行: 用题目的等式或不等式先确定每个变量的取值范围, 再进入循环;
• 由已选变量推出剩余变量: 能算出来的量不再枚举;
• 剪枝: 发现当前分支不可能满足条件时立即跳出循环;

如何用枚举求解平方和三元组？

• 题目: 统计满足 $a^2 + b^2 = c^2$ 且 $1 \le a, b, c \le n$ 的三元组数量;
• 枚举: $a$ 与 $b$ 各枚举 $[1, n]$;
• 推出: 由 $a^2 + b^2$ 直接算出 $c$, 不再枚举第三个变量;
• 判定: $c$ 为整数且 $c \le n$ 时计数加一;

const countTriples = (n) => {
  let res = 0;
  for (let a = 1; a <= n; a++) {
    for (let b = 1; b <= n; b++) {
      const c2 = a * a + b * b;
      const c = Math.floor(Math.sqrt(c2));
      if (c * c === c2 && c <= n) res++;
    }
  }
  return res;
};

• 复杂度: 时间 $O(n^2)$, 空间 $O(1)$;
• 对比: 若 $c$ 也参与枚举则退化为 $O(n^3)$, 由已选变量推出 $c$ 是本题的优化点;