<p>Given a string <code>num</code> that contains only digits and an integer <code>target</code>, return <em><strong>all possibilities</strong> to insert the binary operators </em><code>&#39;+&#39;</code><em>, </em><code>&#39;-&#39;</code><em>, and/or </em><code>&#39;*&#39;</code><em> between the digits of </em><code>num</code><em> so that the resultant expression evaluates to the </em><code>target</code><em> value</em>.</p>

<p>Note that operands in the returned expressions <strong>should not</strong> contain leading zeros.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;123&quot;, target = 6
<strong>Output:</strong> [&quot;1*2*3&quot;,&quot;1+2+3&quot;]
<strong>Explanation:</strong> Both &quot;1*2*3&quot; and &quot;1+2+3&quot; evaluate to 6.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;232&quot;, target = 8
<strong>Output:</strong> [&quot;2*3+2&quot;,&quot;2+3*2&quot;]
<strong>Explanation:</strong> Both &quot;2*3+2&quot; and &quot;2+3*2&quot; evaluate to 8.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> num = &quot;3456237490&quot;, target = 9191
<strong>Output:</strong> []
<strong>Explanation:</strong> There are no expressions that can be created from &quot;3456237490&quot; to evaluate to 9191.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= num.length &lt;= 10</code></li>
	<li><code>num</code> consists of only digits.</li>
	<li><code>-2<sup>31</sup> &lt;= target &lt;= 2<sup>31</sup> - 1</code></li>
</ul>

class Solution {
private:
	vector<long long> nums;
	vector<string> mem;
	vector<string> answer;
	int target;
	long long sum = 0;
public:
	void add()
	{
		string ans;
		ans.reserve(nums.size() * 2);
		for (int i = 0; i < (int)nums.size() - 1; i++)
		{
			ans.append(to_string(nums[i]));
			ans.append(mem[i]);
		}
		ans.append(to_string(nums[(int)nums.size() - 1]));
		answer.push_back(ans);
	}
	void brut(int u,long long cap,long long lust, int zn = 1)
	{
		if (u == nums.size()-1)
		{
			sum += zn*cap;
			if (sum == target) add();
			sum -= zn * cap;
		}
		else
		{
			for (int i = 0; i < 4; i++)
			{
				switch (i)
				{
				case 0:
				{
					sum += zn*cap;
					mem[u] = "+";
					brut(u + 1, nums[u + 1], nums[u+1]);
					sum -= zn*cap;
					break;
				}
				case 1:
				{
					sum += zn * cap;
					mem[u] = "-";
					brut(u + 1, nums[u + 1], nums[u + 1], -1);
					sum -= zn*cap;
					break;
				}
				case 2:
				{
					mem[u] = "*";
					brut(u + 1, cap*nums[u + 1], nums[u + 1], zn);
					break;
				}
				case 3:
				{
                    if(lust==0) break;
					mem[u] = "";
					brut(u + 1,cap/lust*(lust*10+nums[u+1]), lust * 10 + nums[u + 1], zn);
					break;
				}
				}
			}
		}
	}
	vector<string> addOperators(string num, int target) {
		for (auto c : num) nums.push_back(c - '0');
		this->target = target;
		mem.resize(num.size() - 1);
		brut(0, nums[0], nums[0]);
		return answer;
	}
};
18028