416. Partition Equal Subset Sum

題目網址：https://leetcode.cn/problems/partition-equal-subset-sum/

題意：給一只含正整數的非空 array nums, 返回是否能將 nums 切割成兩個 subset, 使得兩個 subset 的元素和相等。

Solution 1：

想法：利用 DP, 因為此題可看作是 0-1 背包問題, 從前 i 個數中取出一些數, 使這些數之和為 target, 其中 dp[i][j] 代表前 i 個數是否能取出一些數, 使得這些數和為 j, 可得以下公式：

• 不選擇 nums[i]：dp[i][j] = dp[i - 1][j]
• 選擇 nums[i]：dp[i][j] = dp[i - 1][j - nums[i]], 其中 j >= nums[i]

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) {
            return false;
        }

        const int target = sum / 2;
        const int maxNum = *max_element(nums.begin(), nums.end());
        if (maxNum > target) {
            return false;
        }

        const int n = nums.size();
        vector<vector<bool>> dp(n, vector<bool>(target + 1, false));

        // dp[i][0] 皆為 true, 因為前 i 個數都不取, 必滿足 sum = 0
        for (int i = 0; i < n; ++i) {
            dp[i][0] = true;
        }

        for (int i = 1; i < n; ++i) {
            for (int j = 1; j <= target; ++j) {
                if (j >= nums[i]) {
                    dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i]];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        return dp[n - 1][target];
    }
};

• time：$O(n \cdot sum)$ ➔ for loop, 因為 target = $\dfrac{sum}{2}$
• space：$O(n \cdot sum)$ ➔ dp

Solution 2：

想法：改進 Solution 1, 因為 dp[i][j] 只會用到上一列的元素, 故不需要開到 $O(n \cdot sum)$ 空間, 只需記住上一列的狀態即可, 這樣只需要 $O(2 \cdot sum)$ space

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) {
            return false;
        }

        const int target = sum / 2;
        const int maxNum = *max_element(nums.begin(), nums.end());
        if (maxNum > target) {
            return false;
        }

        const int n = nums.size();
        vector<bool> dp(target + 1, false);
        dp[0] = true; // dp[0] 為 true, 因為前 i 個數都不取, 必滿足 sum = 0

        for (int i = 1; i < n; ++i) {
            vector<bool> nextRow = dp;
            for (int j = 1; j <= target; ++j) {
                if (j >= nums[i]) {
                    nextRow[j] = dp[j] || dp[j - nums[i]];
                } else {
                    nextRow[j] = dp[j];
                }
            }
            dp = move(nextRow);
        }

        return dp[target];
    }
};

• time：$O(n \cdot sum)$ ➔ for loop, 因為 target = $\dfrac{sum}{2}$
• space：$O(sum)$ ➔ dp 和 nextRow

Solution 3：

想法：改進 Solution 2, 將空間從 2 * sum 降到 sum, 其中 j 的 for loop 必須從後面來, 這樣才不會在同一次 loop 中用到剛賦值的

e.g. nums = [2, 2, 3, 5], target = 6, 沒解

• 順著來：i = 1

  • j = 2 時, dp[i][2] = true

  • j = 4 時, dp[i][4] = dp[i][2] = true

  • j = 6 時, dp[i][6] = dp[i][4] = true, 不符答案

    0	1	2	3	4	5	6
    T	F	T	F	T	F	T

• 倒著來：i = 1

  • j = 6 時, dp[i][6] = dp[i][4] = false

  • j = 4 時, dp[i][4] = dp[i][2] = false

  • j = 2 時, dp[i][2] = dp[i][0] = true

    0	1	2	3	4	5	6
    T	F	T	F	F	F	F

  • 最終輸出為：下表, 得到答案為 false

    0	1	2	3	4	5	6
    T	F	T	T(i=3)	T(i=2)	T(i=4)	F

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        const int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 == 1) {
            return false;
        }

        const int target = sum / 2;
        const int maxNum = *max_element(nums.begin(), nums.end());

        if (maxNum > target) {
            return false;
        }

        const int n = nums.size();
        vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int i = 1; i < n; ++i) {
            // 倒著才不會用到在同一個 j loop 中剛賦值完的
            for (int j = target; j >= 0; --j) {
                if (j >= nums[i]) {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }

        return dp[target];
    }
};

• time：$O(n \cdot sum)$ ➔ for loop, 因為 target = $\dfrac{sum}{2}$
• space：$O(sum)$ ➔ dp