> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/416.-partition-equal-subset-sum.md).

# 416. Partition Equal Subset Sum

Given a **non-empty** array containing **only positive integers**, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

**Note:**<br>

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

**Example 1:**

```
Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
```

**Example 2:**

```
Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.
```

{% hint style="info" %}
既然要找到兩個子集合的和相等，所以所有數字的總合不能是奇數。

dp\[i]\[j]代表nums array裡index = 0到index = i - 1的數字中能否組成和為j的子集合。

DP state transition:\
dp\[i]\[j] = dp\[i - 1]\[j] || dp\[i - 1]\[j - nums\[i - 1]] if j >= nums\[i - 1]\
dp\[i]\[j] = dp\[i - 1]\[j] if j < nums\[i - 1]
{% endhint %}

```cpp
// Bottom-Up Dynamic programming with 2D dp array
bool canPartition(vector<int>& nums) { // time: O(n * sum); space: O(n * sum)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum & 1) return false;
    int target = sum >> 1, n = nums.size();
    // dp[i][j]: whether elements in nums[0...i-1] can form subsets with sum of j
    vector<vector<bool> > dp(n + 1, vector<bool>(target + 1, false)); 
    dp[0][0] = true;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= target; ++j) {
            if (j >= nums[i - 1]) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else { // j < nums[i - 1]
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp.back().back();
}
```

{% hint style="info" %}
仔細觀察可以發現dp\[i]\[j]只需要前一個的row的結果，不需要用到2-D dp array去記錄所有過程，只需要前一排的結果。所以可以只用一個1-D dp array去計算。注意loop target的時候要從大到小，因為這樣才不會重複計算。把2D dp關係式用二維圖形畫出來就顯而易見。
{% endhint %}

```cpp
// Bottom-Up Dynamic programming with 1D DP array
bool canPartition(vector<int>& nums) { // time: O(n * sum); space: O(sum)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum & 1) return false;
    int target = sum >> 1, n = nums.size();
    // dp[i]: whether numbers in nums array can for a subset with sum of i
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = target; j >= nums[i]; --j) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp.back();
}
```

{% hint style="info" %}
Recursion DFS在這比bottom-up DP有效率。
{% endhint %}

```cpp
// DFS
bool helper(vector<int>& nums, int sum, int index) {
    if (index < 0 || sum < nums[index]) return false;
    if (sum == nums[index]) return true;
    return helper(nums, sum - nums[index], index - 1) || helper(nums, sum, index - 1);
}
bool canPartition(vector<int>& nums) { // time: O(2^n); space: O(n)
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum & 1) return false;
    return helper(nums, sum >> 1, nums.size() - 1);
}
```