【JavaScript】バックトラックで階段の上り方を全パターン列挙する方法

問題設定

n段の階段を上ることを考えます。せっかくなので、運動も兼ねて一段ずつ歩くのではなく、ジャンプして登ることにしましょう。

1回のジャンプで進めるのは最大k段まで。ここではkは階段の段数に関係なく、常に1か2であるとします。

課題は、この階段を上り切るために取り得るすべてのジャンプ系列を、ソート済みの配列として返すことです。

入出力例

たとえば n = 4、k = 2 のとき：

climbingStaircase(4, 2)

期待される出力は以下のとおりです。

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]

[1, 1, 1, 1] は毎回1段ジャンプするパターン、[2, 2] は毎回2段ジャンプするパターンを意味します。この場合、合計5通りの上り方が存在します。

バックトラックでの実装方法

すべてのパターンを列挙したい場合は、バックトラック（巻き戻し探索）が定番のアプローチです。各ステップで「1段ジャンプ」「2段ジャンプ」の選択肢を順に試し、残りの段数がちょうど0になった時点でその経路を答えとして記録します。行き詰まったら、直前の選択を取り消して別の分岐へ進みます。

const climbingStaircase = (n, k) => {
  const result = [];
  const path = [];

  const backtrack = (remaining) => {
    // 残り0段 → 完成した経路を保存
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    // 段数を超えていたら打ち切り
    if (remaining < 0) return;

    for (let step = 1; step <= k; step++) {
      path.push(step);             // 選ぶ
      backtrack(remaining - step); // 探索を進める
      path.pop();                  // 選択を戻す（バックトラック）
    }
  };

  backtrack(n);
  return result;
};

console.log(climbingStaircase(4, 2));

実行結果

[
  [1, 1, 1, 1],
  [1, 1, 2],
  [1, 2, 1],
  [2, 1, 1],
  [2, 2]
]

出力は辞書順にソートされており、要件どおりの結果になっています。ただし計算量は解の総数に比例して増えるため、nが大きい場合は処理時間に注意が必要です。

補足：メモ化で「通り数」だけを数える

パターンの列挙ではなく、「何通りあるのか」という数だけが必要なケースもあります。その場合は、メモ化（キャッシュ）付きの再帰で効率よく計算できます。f(n) = f(n-1) + f(n-2) という漸化式に基づく、シンプルな動的計画法です。

const n = 4;

const countWays = (n) => {
  const memo = new Map();
  const recur = (left) => {
    if (left === 1) return 1;
    if (left === 2) return 2;
    if (memo.has(left)) return memo.get(left);
    memo.set(left, recur(left - 1) + recur(left - 2));
    return memo.get(left);
  };
  return recur(n);
};

console.log(countWays(n));

実行結果

5

コンソールには 5 と表示され、先ほど列挙したパターンの総数と一致していることがわかります。

まとめ

• すべての上り方を列挙したい → バックトラック（DFS＋選択の巻き戻し）
• 上り方の個数だけ知りたい → メモ化再帰・動的計画法

目的に応じてこの2つの手法を使い分けることで、階段上り問題は柔軟かつ効率的に解くことができます。