<p>Given an integer array <code>nums</code>, return <code>true</code> <em>if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or </em><code>false</code><em> otherwise</em>.</p>

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

<pre>
<strong>Input:</strong> nums = [1,5,11,5]
<strong>Output:</strong> true
<strong>Explanation:</strong> The array can be partitioned as [1, 5, 5] and [11].
</pre>

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

<pre>
<strong>Input:</strong> nums = [1,2,3,5]
<strong>Output:</strong> false
<strong>Explanation:</strong> The array cannot be partitioned into equal sum subsets.
</pre>

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

<ul>
	<li><code>1 &lt;= nums.length &lt;= 200</code></li>
	<li><code>1 &lt;= nums[i] &lt;= 100</code></li>
</ul>

const static auto _ = [] { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); std::cout.tie(nullptr); return nullptr; }();

class Solution {
public:
   bool recPartitioning(vector<int> &nums, int totalSum, unordered_map<string, bool> &mp, int i ) {
       string s = to_string(i) + to_string(totalSum);
       if(mp.find(s)!= mp.end()) return mp[s];
       if(totalSum == 0) return true;
       if(totalSum < 0  || i == nums.size()) return false;
       mp[s] = recPartitioning(nums, totalSum - nums[i], mp, i+1) || recPartitioning(nums, totalSum, mp, i+1);
       return mp[s];
   }

    bool canPartition(vector<int>& nums) {
        int totalSum  = 0;
        for(auto elm : nums) 
          totalSum += elm;
        if(totalSum % 2 != 0)
           return false;
        unordered_map<string, bool> mp;
        return recPartitioning(nums, totalSum / 2, mp, 0);
    }
};
205403