C++-এ এক্সপ্রেশনে অপারেটর যোগ করে টার্গেট পাওয়া (Expression Add Operators)

এক্সপ্রেশন অ্যাড অপারেটরস সমস্যা

একটি ডিজিট স্ট্রিং num এবং একটি টার্গেট মান দেওয়া আছে। স্ট্রিংয়ের ডিজিটগুলোর মাঝপথে +, -, * অপারেটর যোগ করে টার্গেট মান পাওয়ার সব সম্ভাব্য এক্সপ্রেশন খুঁজে বের করতে হবে।

উদাহরণ: num="232", target=8 → ["2*3+2", "2+3*2"]

সমাধানের পদ্ধতি (ব্যাকট্র্যাকিং / DFS)

• রিকার্সিভ ফাংশন solve(idx, currVal, target, expr, lastMul):
  • idx: বর্তমান সূচক
  • currVal: বর্তমান এক্সপ্রেশনের মান
  • expr: বর্তমান এক্সপ্রেশন স্ট্রিং
  • lastMul: গুণফলের চেইন হ্যান্ডল করার জন্য শেষ গুণ করা মান
• প্রতিটি পজিশনে সম্ভাব্য সব অঙ্কের সমষ্টি (এক বা একাধিক ডিজিট) নিয়ে +, -, * ট্রাই করুন
• লিডিং জিরো এড়ান (যেমন "05" অবৈধ)
• idx == size হলে currVal == target চেক করুন

C++ কোড উদাহরণ

= 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;
    }
};

int main() {
    Solution ob;
    print_vector(ob.addOperators("232", 8));
    return 0;
}

ইনপুট

"232", 8

আউটপুট

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