<p>You are given an integer array <code>nums</code> and an integer <code>target</code>.</p>

<p>You want to build an <strong>expression</strong> out of nums by adding one of the symbols <code>&#39;+&#39;</code> and <code>&#39;-&#39;</code> before each integer in nums and then concatenate all the integers.</p>

<ul>
	<li>For example, if <code>nums = [2, 1]</code>, you can add a <code>&#39;+&#39;</code> before <code>2</code> and a <code>&#39;-&#39;</code> before <code>1</code> and concatenate them to build the expression <code>&quot;+2-1&quot;</code>.</li>
</ul>

<p>Return the number of different <strong>expressions</strong> that you can build, which evaluates to <code>target</code>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,1,1,1,1], target = 3
<strong>Output:</strong> 5
<strong>Explanation:</strong> There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
</pre>

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

<pre>
<strong>Input:</strong> nums = [1], target = 1
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 20</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>
	<li><code>0 &lt;= sum(nums[i]) &lt;= 1000</code></li>
	<li><code>-1000 &lt;= target &lt;= 1000</code></li>
</ul>

struct CacheHasher
{
    std::size_t operator()(const std::pair<int, std::size_t>& key) const
    {
        return std::hash<int>()(key.first) ^ std::hash<std::size_t>()(key.second);
    }
};

using Cache = std::unordered_map<
    std::pair<int, std::size_t>, 
    int,
    CacheHasher>;

class Solution
{
	int countWays(const std::vector<int>& nums, int target, std::size_t idx, Cache& cache)
	{
		if(idx == nums.size())
			return target == 0 ? 1 : 0;

        auto cacheKey = std::make_pair(target, idx);
        if(auto it = cache.find(cacheKey); it != std::end(cache))
            return it->second;
        
		int currNum = nums.at(idx);
		++idx;

		int plusCnt  = countWays(nums, target-currNum, idx, cache);
		int minusCnt = countWays(nums, target+currNum, idx, cache);

		return cache[cacheKey] = plusCnt + minusCnt;
	}

public:
	int findTargetSumWays(vector<int>& nums, int target)
	{
        Cache cache;
		return countWays(nums, target, 0, cache);
	}
};
72943