C++で式に演算子を追加する問題の解法（バックトラッキング）

問題概要

0から9までの数字のみで構成された文字列と、1つの目標値が与えられます。数字の間に二項演算子「+」「-」「*」を挿入し、その式の評価結果が目標値と一致するような、考えられるすべての組み合わせを求めて返すのがこの問題です。

例えば、入力が「232」で目標値が8の場合、答えは ["2*3+2", "2+3*2"] となります。

アルゴリズムの流れ

この問題はバックトラッキング（深さ優先探索）を使って解きます。以下の手順に従います。

• solve() というメソッドを定義します。引数は idx（現在のインデックス）、s（元の数字列）、curr（現在の計算結果）、target（目標値）、temp（構築中の式文字列）、mult（直前に適用した乗算の値）です。
• idx が s のサイズ以上になった場合：
  • curr が target と一致していれば、temp を結果リスト ret の末尾に追加します。
  • その後、処理を終了して戻ります。
• aux を空文字列として初期化します。
• i を idx から s のサイズ未満まで1ずつ増やしながら繰り返します：
  • aux に s[i] を連結します。
  • aux[0] が '0' かつ aux のサイズが1より大きい場合（先頭に余分な0が付く場合）は、以降の処理を無視して次の反復へスキップします。
  • idx が 0 の場合（最初の数値）：solve(i + 1, s, aux を整数に変換した値, target, aux, aux を整数に変換した値) を呼び出します。
  • それ以外の場合：
    • 「+」の場合：solve(i + 1, s, curr + stol(aux), target, temp + "+" + aux, stol(aux)) を呼び出します。
    • 「-」の場合：solve(i + 1, s, curr - stol(aux), target, temp + "-" + aux, -stol(aux)) を呼び出します。
    • 「*」の場合：solve(i + 1, s, curr - mult + mult * stol(aux), target, temp + "*" + aux, mult * stol(aux)) を呼び出します。
• メインメソッドから solve(0, num, 0, target, 空文字列, 0) を呼び出します。
• 最後に ret を返します。

乗算処理のポイント

乗算は加減算より優先順位が高いため、単純に curr に値を掛けることはできません。例えば「2+3」まで計算した状態でさらに「*2」を付けたい場合、正しい結果は「2+3*2」＝8です。そこで、直前に加算・減算した分（mult）を一度巻き戻し、「curr - mult + mult × 新しい値」として再計算することで、演算子の優先順位を正しく反映しています。

実装例

それでは、理解を深めるために以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
       cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
typedef long long int lli;
class Solution {
    public:
    vector <string> ret;
    void solve(int idx, string s, lli curr, lli target, string temp, lli mult){
       //cout << temp << " " << curr << endl;
       if(idx >= s.size()){
          if(target == curr){
             ret.push_back(temp);
          }
          return;
       }
       string aux = "";
       for(int i = idx; i < s.size(); i++){
          aux += s[i];
          if(aux[0] == '0' && aux.size() > 1) continue;
          if(idx == 0){
             solve(i + 1, s, stol(aux), target, aux, stol(aux));
          } else {
             solve(i + 1, s, curr + stol(aux), target, temp + "+" + aux, stol(aux));
             solve(i + 1, s, curr - stol(aux), target, temp + "-" + aux, -stol(aux));
             solve(i + 1, s, curr - mult + mult * stol(aux), target, temp + "*" + aux, mult * stol(aux));
          }
       }
    }
    vector<string> addOperators(string num, int target) {
       solve(0, num, 0, target, "", 0);
       return ret;
    }
};
main(){
    Solution ob;
    print_vector(ob.addOperators("232", 8));
}

入力

"232", 8

出力

[2+3*2, 2*3+2]