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:

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.

既然要找到兩個子集合的和相等，所以所有數字的總合不能是奇數。

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]

// 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();
}

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

// 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();
}

Recursion DFS在這比bottom-up DP有效率。

// 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);
}