基本的な探索アルゴリズムのテンプレート集
再帰を用いた探索手法
再帰は、探索アルゴリズムの実装において非常に強力なツールです。ここでは、いくつかの基本的な列挙問題を再帰関数で解くテンプレートを示します。
部分集合の列挙 (指数型探索)
N個の要素からなる集合のすべての部分集合を生成します。各要素について「含める」か「含めない」かの2つの選択肢があるため、計算量はO(2^N)となります。
#include & ...
10月23日 14:31 投稿
文字列のパリンドローム分割におけるバックトラッキング手法と動的計画法による高速化
問題定義
特定の入力文字列を受け取り、それを複数の部分文字列に分割する際、各部分文字列が必ずパリンドローム（読み返しても同一になる列）となるようなすべての組み合わせを求めるタスクです。
探索アプローチの設計
この種の分割問題は、標準的なループ制御のみで実装しようとすると境界条件や重複チェックが複雑化しやすくなります。代わりに、選択枝を並木道のよう ...
8月21日 12:55 投稿
バックトラッキングアルゴリズムとその応用問題
組合せ問題（Leetcode77）
// アプローチ: 1からnまでの数を再帰的に探索し、リストでk個の組み合わせが作成されたかを記録
// 各ループの開始値が前の値と重複しないように、開始インデックスを設定
class Solution {
private List<List<Integer>> 結果;
private List<Integer> 現在の組み合わせ;
private int 目標サイズ;
public ...
7月2日 17:53 投稿
Javaリストデータの順列生成アルゴリズム
Javaにおけるリスト要素の順列生成
与えられたリストの全要素を使用する順列（全ての可能な並び順）を生成する方法について解説します。ここでは再帰的アプローチを用いた実装を示します。
実装コード
import java.util.ArrayList;
import java.util.List;
public class PermutationGenerator {
public static List<List<Integer>> generateAllPerm ...
5月22日 20:59 投稿
アルゴリズム問題 - バックトラッキング手法
1.バックトラッキングの理論的基礎
1.1バックトラッキングとは何か
バックトラッキングは探索アルゴリズムの一種であり、再帰処理に基づいて動作します。
再帰呼び出しの結果としてバックトラッキングが発生するため、再帰があれば必ずバックトラッキングも存在します。
1.2バックトラッキングの性能
バックトラッキングは計算効率が悪いという特徴があります。これは、す ...
5月20日 01:32 投稿
LeetCode解説：216.組合せ総和IIIと17.電話番号の文字列組み合わせ [バックトラッキング編]
LeetCode 216.組合せ総和III
問題リンク：216.組合せ総和III
問題説明
1から9までの数字からk個の数字を選び、その合計がnとなるすべての有効な組み合わせを見つけます。以下の条件を満たす必要があります：
使用できる数字は1から9まで
各数字は最大で1回まで使用可能
結果には重複する組み合わせを含めない
例1：
入力：k = 3, n = 7
出力: [[1,2,4]]
説明: 1 + 2 + ...
5月18日 15:03 投稿