バックトラック法を用いた組み合わせ合計問題の解法
39. 組み合わせ合計問題（重複選択可）
整数配列candidatesと目標値targetが与えられたとき、配列要素の和がtargetとなる全てのユニークな組み合わせを返します。各要素は無制限に再利用可能です。
入力例: candidates = [2,3,6,7], target = 7
出力例: [[2,2,3],[7]]
解法ポイント:
要素の重複使用を許可するため、再帰呼び出し時にインデックスを進めない
枝刈り処 ...
8月1日 05:05 投稿
バックトラックアルゴリズムの理論と組み合わせ問題の実装
バックトラック法の基本概念
バックトラック法は探索手法の一種で、再帰処理と密接に関連しています。再帰処理を行う際には必ずバックトラックが発生するため、バックトラックは再帰の副産物と言えます。
バックトラック法の効率性
バックトラック法は本質的に全探索アルゴリズムであり、効率的とは言えません。ただし、枝刈り(pruning)を適用することで多少の効率改善 ...
7月16日 16:50 投稿
3×3グリッド全点灯における最小操作手数求解アルゴリズム
問題概要
3行3列のマトリックス状に配置された9つの照明スイッチがある。各スイッチを操作すると、該当する位置および上下左右に隣接するセルの電球状態が反転する（ON⇔OFF）。初期状態の入力が与えられた際、すべてのセルをON状態に切り替えるための最小操作回数を求めよ。
入力・出力仕様
標準入力からは3行にわたり、各行3個の整数が半角スペース区切りで渡される。各 ...
6月29日 21:46 投稿