C++で多数を等しい合計の2つ以上のセグメントに分割できるかどうかを確認します

ここでは、数値を同じ合計で複数のセグメントに分割できるかどうかを確認できるプログラムを確認します。数値が74325のようなものであるとすると、これは3つの部分（7）、（4、3）、（2、5）に分割でき、すべて同じum値になります。

この問題を解決するには、次の手順に従う必要があります。

• 数字を文字列として取ります
• 配列を使用して、配列のプレフィックス合計を保持します
• これで、2番目の要素から最後の要素に移動し、最初のセグメントは0からi-1になり、その合計はprefix_sum[i-1]に配置されます
• 1からnまでトラバースする別の変数を使用してから、合計を加算し続けます。
• 合計値がいずれかの段階でprefix_sum[i– 1]と同じである場合、セグメントの合計は最初の値と等しくなります。
• セグメント合計値を0に再初期化してから、ポインターを動かし続けます。
• いずれかの段階でセグメントの合計がprefix_sum[i– 1]より大きい場合は、ループを中断します
• 最後の宛先に到達し、最後のセグメントの合計が最初のセグメントの合計と同じである場合、それを等しい合計のセグメントに分割できます。

例

#include <iostream>
using namespace std;
bool canBeSegmented(string str) {
   int n = str.length();
   int prefix_sum[n];
   prefix_sum[0] = str[0] - '0';
   for (int i = 1; i < n; i++) {
      prefix_sum[i] = prefix_sum[i - 1] + (str[i] - '0');
   }
   for (int i = 1; i <= n - 1; i++) {
      int sum = prefix_sum[i - 1];
      int prev_sum = 0;
      int it = i;
      bool flag = false;
      while (it < n) {
         prev_sum += str[it] - '0';
         if (prev_sum == sum) {
            prev_sum = 0;
            flag = true;
         } else if (prev_sum > sum) {
            break;
         }
         it++;
      }
      if (prev_sum == 0 && it == n && flag) {
         return true;
      }
   }
   return false;
}
int main() {
   string s = "74325";
   if (canBeSegmented(s))
      cout << "Yes, This can be segmented into more than two segments";
   else
      cout << "No, This can not be segmented into more than two segments";
}

出力

Yes, This can be segmented into more than two segments