深さ優先探索（Depth-First Search）

ある状態からはじめて、遷移できなくなるまで状態を進める。
遷移できなくなったら1つ前の状態に戻る。
上記はstackのpushとpopで実現できる。
このため、深さ優先探索は再帰関数（呼び出し元に戻る）で実装できる場合が多い。

部分和問題（Partial Sum）

{a₁, a₂, ..., a_n}からいくつか選んだ和がkになるかを判別する。
今回は深さ優先探索で各組み合わせの和をすべて求める。
a₁から順に和に加えないor加えるを決める。
このため、以下のような二分木に対して、深さ優先探索を行えば良い。

public class PartialSum
{
  internal List<int> PartialSums = new();
  internal List<int> Numbers;
  
  public PartialSum(List<int> numbers)
  {
    this.Numbers = numbers;
  }
  
  public List<int> GetPartialSums()
  {
    this.ParsePartialSums(0, 0);
    return this.PartialSums;
  }
  
  private void ParsePartialSums(int i, int sum)
  {
    if (i == Numbers.Count)
    {
      this.PartialSums.Add(sum); // 葉に到着（これ以上遷移不可能）の場合は終了
      return;
    }
  
    ParsePartialSums(i + 1, sum); // 合計値にi番目の値を加えない
  
    ParsePartialSums(i + 1, sum + this.Numbers.ElementAt(i)); // 合計値にi番目の値を加える
  }
}

ナップサック問題（Knapsack Problem）

部分和の対象が以下のような『重量と価値の組』になる。
{ (w₁, v₁), (w₂, v₂), ..., (w_n, v_n)}

public class KnapsackProblem
{
  internal List<(int weight, int value)> WeightValues;
  internal int LimitWeight;
  
  internal List<(int weight, int value)> SumWeightValue = new();
  
  public KnapsackProblem(List<(int weight, int value)> weightValues, int limitWeight)
  {
    this.WeightValues = weightValues;
    this.LimitWeight = limitWeight;
  }
  
  public List<(int weight, int value)> GetSumWeightValue()
  {
    this.CreateWumWeightValue(0, 0, 0);
    return this.SumWeightValue;
  }
  
  private void CreateWumWeightValue(int i, int weight, int value)
  {
    if (i == WeightValues.Count)
    {
      this.SumWeightValue.Add((weight, value));
      return;
    }
  
    CreateWumWeightValue(i + 1, weight, value);
  
    CreateWumWeightValue(i + 1, weight + WeightValues.ElementAt(i).weight, value + WeightValues.ElementAt(i).value);
  }
}

迷路

スタート（S）とゴール(G)のほかに道(.)と壁(#)からなる地図で、ゴールまで辿り着けるか。

S.#.
..#G
....

深さ優先探索を用いて、以下のように隣接する縦・横・斜めの道を進む。

上記のように探索するためには、左斜め上は現在地から(-1, -1)、上は(0, -1)...なので以下のようになる。

以上より、コードは以下のようになる。

private void CanReachToGoalByRecursive(int row, int col)
{
  if (this.CanReachToTheGoal) return;
  this.Map[row, col] = ALREADY_VISITED;

  for (var adjacentRow = -1; adjacentRow <= 1; ++adjacentRow)
  {
    var nextRow = row + adjacentRow;
    var inRowRange = nextRow >= 0 && nextRow < H; // 縦方向に地図内に収まっている
    if (!inRowRange) continue;
    for (var adjacentCol = -1; adjacentCol <= 1; ++adjacentCol)
    {
      var nextCol = col + adjacentCol;
      var inColRange = nextCol >= 0 && nextCol < W; // 横方向に地図内に収まっている
      if (!inColRange) continue;
      var nextPlace = this.Map[nextRow, nextCol];
      if (nextPlace == GOAL)
      {
        this.CanReachToTheGoal = true;
        return;
      }
      if (nextPlace == ROAD)
        CanReachToGoalByRecursive(nextRow, nextCol); // 次が道であれば進む
    }
  }
}