Dart部分和問題の解き方

競技プログラミングで頻出する再帰関数、メモ化、全探索を使用し、部分和問題の解き方について解説して行こうと思います。

自分のアウトプットを目的として今回の記事を書いています。
⚠️メモ化に関しては最後のフィボナッチ数列の例で解説させて頂きます。

再帰関数とは

再帰関数とは関数の中で呼び出される関数のことで、関数の中での処理が終了するまで、永遠と実行を繰り返す関数になっています。for文と似ています。

forループでの例：

void main() {
  print(iterativeSum(5));
}

int iterativeSum(int n) {
  int temp = 0;

  for (int i = 0; i <= n; i++) {
    temp += i;
  }

  return temp;
}

再帰関数での例：

void main() {
  print(recursiveSum(5));
}

int recursiveSum(int n) {
  if (n <= 0) {
    return 0;
  }

  return n + recursiveSum(n - 1);
}

このように再帰関数の中ではreturnの際recursiveSumを再度呼び出していることがわかります。この時注目して欲しいことがその際nの値を変化させているということ、これより同じrecursiveSumの呼び出しでも値が変わっていっています。
この時の出力も載せておきます

5 + recursiveSum(4)
=> 5 + ( 4 + recursiveSum(3) )
=> 5 + ( 4 + ( 3 +recursiveSum(2) ) )
=> 5 + ( 4 + ( 3 +  ( 2 + recursiveSum(1) ) ) )
=> 5 + ( 4 + ( 3 +  ( 2 + ( 1 + recursiveSum(0) ) ) ) )
=> 5 + ( 4 + ( 3 +  ( 2 + ( 1 + 0 ) ) ) )
=> 15

全探索とは

全探索とはしらみつぶしにすべての組み合わせを調べ、その中から解をさがす方法です。
この言葉に関しては意味を理解していれば大丈夫です。すべての基本となる技なので慣れておくと競技プログラミングで活躍するかもしれません。

フィボナッチ数列とは

イタリアの数学者フィボナッチ(1170~1259年頃)が紹介した数列を「フィボナッチ数列」と言います。 １、１、２、３、５、８、１３、２１、３４、５５、８９、１４４、２３３、３７７… 「どの数字も前２つの数字を足した数字」という規則の数列です。
こちらをつかって解く問題をやっていこうと思います。

部分話問題とは

定義：
部分和問題（ぶぶんわもんだい）は、計算複雑性理論・暗号理論における問題で、与えられた n 個の整数 a1,...,an から部分集合をうまく選んで、その集合内の数の和が与えられた数 N に等しくなるようにできるかどうかを判定する問題である。
このように定義されています。その上で以下に問題を記します。

𝑁 個の数 a1,a2,...aN-1と正の整数Wが与えられ、a0,a1,...aN-1の中から何個かの整数を選んで総和をWとすることができるか判定しなさい。

回答例：

void main() {
  List<int> numbers = [2, 4, 6, 8];
  int targetSum = 10;

  if (canSum(numbers, targetSum)) {
    print("総和 $targetSum を作成できます。");
  } else {
    print("総和 $targetSum を作成できません。");
  }
}

bool canSum(List<int> numbers, int targetSum) {
  //条件分岐
  if (targetSum == 0) {
  }
  if (targetSum < 0) {
  }
  if (numbers.isEmpty) {
  }
  
  int lastNumber = numbers.last;
  List<int> remainingNumbers = numbers.sublist(0, numbers.length - 1);
  bool includeLast = canSum(remainingNumbers, targetSum - lastNumber);
  bool excludeLast = canSum(remainingNumbers, targetSum);

  return includeLast || excludeLast;
} 

こちらが解答例になります。
部分的に解説していこうと思います。

mainの実行

void main() {
  List<int> numbers = [2, 4, 6, 8];
  int targetSum = 10;

  if (canSum(numbers, targetSum)) {
    print("総和 $targetSum を作成できます。");
  } else {
    print("総和 $targetSum を作成できません。");
  }
}

まずnmbersリスト、taegetSumの方を作成します。その後Cansumという関数を実行します。

CanSum関数

bool canSum(List<int> numbers, int targetSum) {
  //条件分岐
  if (targetSum == 0) {
    return true; // 総和が0になった場合、成功
  }
  if (targetSum < 0) {
    return false; // 総和が負の値になった場合、失敗
  }
  if (numbers.isEmpty) {
    return false; // 整数が残っていない場合、失敗
  }
  
  int lastNumber = numbers.last;
  List<int> remainingNumbers = numbers.sublist(0, numbers.length - 1);

  //再帰関数
  //最後の値を含めるか含めないか
  //includeLastはtargetSumの値がlastNumberにより再帰される度に減少していく
  bool includeLast = canSum(remainingNumbers, targetSum - lastNumber);
  bool excludeLast = canSum(remainingNumbers, targetSum);


  return includeLast || excludeLast;
} 

最後の行についての解説

このメソッドにより、再帰関数の中で実行が繰り返されtargetSumが判定可能かどうかを実行します。
また、問題の最後に、includeLast || excludeLast;の行で、どちらかの条件がtrueになるまで処理を抜けません

メモ化

キャッシュとも言われ、remainingNumbersで前回のnumbersを記憶し、無駄な処理をしなようになっています。
これがいわゆるメモ化です

最後の値を含めるか含めないか

この問題の中で、肝となる部分として、includeLast、excludeLastの部分を見ていこうと思います。計算の
中でまず、部分和問題では、ナップサック問題に含まれるため、動的計画法の手法で解くことができます。
その上でこうした問題において、この最後の値を含めるか含めないかという考慮をすることで、すべての組み合わせをためすことが可能となります。

動的計画法

定義:
対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。そこで今回の場合メモ化を利用し同じ計算を防ぐことで、計算時間を削減しています。remainingNumbersを記憶しています。