<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>

class Solution {
public:
    // Analysis
    // method1: greedy (DP..)
    // step1: sort the array, then pick the last one, ...
    // -- 其实不用排序也行的，无非就是随机挑选(the last...)
    // -- 复杂度(N * N * sum);

    // Optimization: 优化
    // 从尾部开始判断，是否要(1-不取；0-取)
    // 那么复杂度就是2 (每个问题判断两次)，也就是(N*sum);
    
    bool canPartition(vector<int>& nums) {
        // sort(nums.begin(), nums.end());

        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (sum % 2) return false;

        cout << "sum:" << sum << " nums size: " << nums.size() << endl;

        return canPartition(nums, nums.size()-1, sum / 2);
    }

    // bool canPartition(vector<int>& nums, int idx, int val) {

    //     string key = to_string(idx) + "_" + to_string(val);
    //     auto iter = m_values.find(key);
    //     if (iter != m_values.end()) return iter->second;

    //     // cout << "idx:" << idx << " val: " << val << endl;
    //     if (val == 0) return true;
    //     if (val < 0) return false;
    //     if (idx < 0) return false;

    //     for (int i = 0; i <= idx; i++) {
    //         if ((val - nums[i]) < 0) continue;

    //         if (canPartition(nums, i-1, val - nums[i])) {
    //             m_values[key] = true;
    //             return true;
    //         }
    //     }

    //     m_values[key] = false;
    //     return false;
    // }

    map<string, bool> m_values;

    bool canPartition(vector<int>& nums, int idx, int val) {

        string key = to_string(idx) + "_" + to_string(val);
        auto iter = m_memo.find(key);
        if (iter != m_memo.end()) return iter->second;

        // cout << "idx:" << idx << " val: " << val << endl;
        if (val == 0) return true;
        if (val < 0) return false;
        if (idx < 0) return false;

       bool result =  canPartition(nums, idx-1, val - nums[idx]) || 
                      canPartition(nums, idx-1, val);
       m_memo[key] = result;
       return result;
    }

    map<string, bool> m_memo;
};
108035