【C++】ターゲット値に一致するすべての式を生成して出力する方法

問題の概要

この問題では、0〜9の数字からなる文字列とターゲット値が与えられます。数字の間に「+」「-」「*」の演算子を挿入して作成できる式のうち、評価結果がターゲット値と等しくなるものをすべて出力することが求められます。

具体例

まず、例を見ながら問題を理解しましょう。

入力: string = "123"、target = 6
出力: { "1+2+3", "1*2*3" }

解法のアプローチ

この問題は、数字の間に挿入できるすべての二項演算子の組み合わせで式を生成し、その評価結果がターゲット値と一致するかどうかを確認することで解くことができます。

具体的には、再帰的な関数にすべての候補となる値を渡しながら式を評価していきます。なお、数値が「0」で始まる場合(例えば「05」のような先頭に余分なゼロを含む数)は無効な表現として無視します。

アルゴリズムのポイント

• 各位置から部分文字列(数値)を切り出し、演算子を挟んで再帰的に探索を進めます。
• 乗算「*」を処理する際は、直前の演算結果(last)を記録しておき、「現在値 - last + last × cur」と計算することで、演算子の優先順位を正しく反映できます。
• 減算の場合は last に負の値(-cur)を渡すことで、後続の乗算処理にも正しく対応できます。

計算量については、隣り合う数字の間ごとに「+」「-」「*」「連結(演算子なし)」の4通りの選択肢があるため、桁数を n とすると最大でおよそ O(4ⁿ) の組み合わせを探索することになります。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
void generateExpressionForTarget(vector<string>& res, string curExp,
string input, int target, int pos,int curVal, int last){
   if (pos == input.length()){
      if (curVal == target)
         res.push_back(curExp);
      return;
   }
   for (int i = pos; i < input.length(); i++){
      if (i != pos && input[pos] == '0')
         break;
      string part = input.substr(pos, i + 1 - pos);
      int cur = atoi(part.c_str());
      if (pos == 0)
         generateExpressionForTarget(res, curExp + part, input, target, i + 1, cur, cur);
      else{
         generateExpressionForTarget(res, curExp + "+" + part, input, target, i + 1, curVal + cur, cur);
         generateExpressionForTarget(res, curExp + "-" + part, input, target, i + 1, curVal - cur, -cur);
         generateExpressionForTarget(res, curExp + "*" + part, input, target, i + 1, curVal - last + last * cur, last * cur);
      }
   }
}
vector<string>generateExpression(string input, int target){
   vector<string> res;
   generateExpressionForTarget(res, "", input, target, 0, 0, 0);
   return res;
}
int main(){
   string input = "345";
   int target = 12;
   cout<<"The expressions are: \n";
   vector<string> res = generateExpression(input, target);
   for (int i = 0; i < res.size(); i++)
   cout << res[i] << " ";
   cout << endl;
   return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

The expressions are −
3+4+5

この結果は、文字列 "345" に対してターゲット値 12 になる式が「3+4+5」(3+4+5 = 12)のみであることを示しています。「3*4」も 12 になりますが、残りの数字「5」を使っていないため条件を満たさず、出力には含まれません。