# 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);
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dynamic-programming/416.-partition-equal-subset-sum.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.