全探索とbit全探索 — すべての解法の出発点

Part 3は解法パターン編です。初回は全探索（brute force）——「候補を全部試す」という、最も素朴で最も重要な解法から始めます。

学習者

全部試すって、それ「アルゴリズム」なの…？工夫がないというか、力任せというか。

それがれっきとしたアルゴリズムなんです。理由は2つあります。第一に、制約が小さければ全探索が正解です。第2章の表を思い出してください——N ≤ 20なら2^N通り試してよいと、出題者が制約で言っています。第二に、貪欲法もDPも「全探索の無駄を削ったもの」です。まず全探索で解ける形にしてから削るのが、応用解法への正しい登り方です。

型1: 多重ループの全探索

問題: N個の商品から3つ選んで、合計がちょうどX円になる組み合わせはあるか。（N ≤ 100）

100個から3つ選ぶ組み合わせは約16万通り。10^8に遠く及ばないので全部試します。

function hasTriple(prices: number[], x: number): boolean {
  const n = prices.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {       // j は i+1 から（重複選択を防ぐ）
      for (let k = j + 1; k < n; k++) {
        if (prices[i] + prices[j] + prices[k] === x) return true;
      }
    }
  }
  return false;
}

「組み合わせ（順序なし）」は j = i + 1 から始めて重複を避ける——この添字の切り方は頻出イディオムです。3重ループはO(N³)なので、N ≤ 500くらいまでが目安です。

型2: 順列の全列挙

「並べ方を全部試したい」ときは順列の列挙です。N ≤ 10なら10! ≈ 363万通りで間に合います。

問題: N個の都市をすべて1回ずつ巡るとき、移動距離の合計の最小値を求めよ。（N ≤ 8、巡回セールスマン問題の小規模版）

function permutations<T>(arr: T[]): T[][] {
  if (arr.length <= 1) return [arr];
  const result: T[][] = [];
  for (let i = 0; i < arr.length; i++) {
    const rest = [...arr.slice(0, i), ...arr.slice(i + 1)];
    for (const p of permutations(rest)) {
      result.push([arr[i], ...p]);        // 先頭を固定して残りの順列を再帰生成
    }
  }
  return result;
}
 
// 全順列について距離を計算し、最小を取る
let best = Infinity;
for (const route of permutations(cities)) {
  best = Math.min(best, totalDistance(route));
}

順列生成は再帰の練習台としても優秀です。「先頭を1つ選ぶ→残りで同じ問題を解く」という再帰の分解は、後のDFS・バックトラッキングにそのままつながります。

型3: bit全探索 — この章の主役

「N個のものそれぞれについて、選ぶ/選ばない」の2^N通りを試す方法です。AtCoder ABCのC問題常連で、paizaのAランクでも顔を出します。

鍵になるのは、整数のビット列を「選び方」とみなす発想です。

N = 3 のとき、0〜7 の整数がそのまま8通りの選び方に対応する

  整数  2進数   意味
  0     000    何も選ばない
  1     001    0番目だけ選ぶ
  5     101    0番目と2番目を選ぶ
  7     111    全部選ぶ

問題: N個の数から好きな個数選んで、合計をちょうどXにできるか。（N ≤ 20）

N ≤ 20 は「2^20 ≈ 100万通り、試してよし」の合図です（第2章の表）。

function canMakeSum(nums: number[], x: number): boolean {
  const n = nums.length;
  for (let bit = 0; bit < (1 << n); bit++) {   // 1 << n は 2^n
    let sum = 0;
    for (let i = 0; i < n; i++) {
      if (bit & (1 << i)) sum += nums[i];      // bitのi桁目が立っていたらi番目を選ぶ
    }
    if (sum === x) return true;
  }
  return false;
}

使うビット演算は2つだけです。

計算量はO(2^N × N)。N = 20で約2,000万、ぎりぎり余裕です。「部分集合」「選ぶ/選ばない」「N ≤ 20前後」の三点セットが揃ったらbit全探索——これは最も再現性の高いパターン認識の1つです。

全探索から他の解法への橋

冒頭で「応用解法は全探索の無駄削り」と言いました。この見取り図を持っておくと、Part 3の残りがつながって見えます。

面接でも「まず全探索ならO(2^N)です。ただ同じ部分問題を何度も解いているので、DPでO(NX)に落とせます」という全探索起点の説明は、思考の筋道が伝わる強い型です。

メンター

上級者ほど「これは全探索で間に合うか？」を最初に確認します。間に合うなら凝った解法は不要——シンプルな全探索はバグも少なく、テスト本番では正義です。「賢い解法を書きたい」誘惑に勝つのも実力のうちですよ。

この章のパターンの見分け方

まとめ

• 全探索は「力任せ」ではなく、制約が許すなら最優先で選ぶべき解法。バグりにくさは正義
• 組み合わせの多重ループは j = i + 1 開始で重複を防ぐ
• bit全探索: 整数0〜2^N-1を「選び方」とみなす。1 << i と bit & (1 << i) の2演算だけで書ける
• 「選ぶ/選ばない × N ≤ 20」はbit全探索の三点セット
• 貪欲法・DP・二分探索は全探索の無駄を削った姿。まず全探索で考えてから削る

次章は「候補を半分ずつ捨てる」削り方——ソートと二分探索です。「答えで二分探索する」という発想の転換まで進みます。