# 416 - Partition Equal Subset Sum

解法一 - 暴力法 (Recursive function)

這題的暴力想法就是，每遇到一個 element，都可以決定要不要把這個 element 加進目前的 subset（是不是跟 0/1 背包問題很像呢？都是每遇到一個 item 都可以分成要不要把目前這個 item 加入背包），如果可以找到一個 subset sum 是原本 array sum 的一半，那剩下的就可以形成另一個 subset，而且 sum 也是原本 array sum 的一半。

實作如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;

        for(auto n: nums)
            sum += n;

        // If sum is odd, it's impossible to have two subsets with equal sum
        if(sum % 2 != 0)
            return false;

        return recursivePartition(nums, sum/2, 0);
    }

private:
    bool recursivePartition(vector<int>& nums, int sum, int curIdx) {
        if(sum == 0)
            return true;

        if(nums.size() == 0 || curIdx >= nums.size())
            return false;

        // Use the value of curIdx
        if(nums[curIdx] <= sum) {
            if(recursivePartition(nums, sum-nums[curIdx], curIdx+1)) 
                return true;
        }

        // Don't use the value of curIdx
        return recursivePartition(nums, sum, curIdx+1);
    }
};

不意外地，上面的方法會 TLE。

解法二 - Recursive + Memoization

要改善上面的方法，就是要用另一個 array 來儲存 function 的計算結果。因為我們同時要考慮 sum 跟 curIdx 兩個變數，所以需要用一個 2D 的 table 來儲存。雖然我們的 table 裡面只需要存 true or false，但為了區分目前這格有沒有被算過，我們還是用 int 來存，-1 表示沒算過，0/1 表示 false/true。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;

        for(auto n: nums)
            sum += n;

        // If sum is odd, it's impossible to have two subsets with equal sum
        if(sum % 2 != 0)
            return false;

        vector<vector<int>> memo(sum/2+1, vector<int>(nums.size(), -1));

        return recursivePartition(nums, sum/2, 0, memo);
    }

private:
    bool recursivePartition(vector<int>& nums, int sum, int curIdx, vector<vector<int>>& memo) {
        if(sum == 0) {
            return true;
        }

        if(nums.empty() || curIdx >= nums.size())
            return false;

        if(memo[sum][curIdx] == -1) {
            if(nums[curIdx] <= sum) {
                // Use the value of curIdx
                if(recursivePartition(nums, sum-nums[curIdx], curIdx+1, memo)) {
                    memo[sum][curIdx] = 1;
                    return true;
                }
            }

            // Don't use the value of curIdx
            memo[sum][curIdx] = recursivePartition(nums, sum, curIdx+1, memo) ? 1 : 0;
        }

        return memo[sum][curIdx] == 1 ? true : false;
    }
};

參考一下執行效率：

Runtime: 40 ms, faster than 72.06% of C++ online submissions for Partition Equal Subset Sum. Memory Usage: 69.3 MB, less than 5.88% of C++ online submissions for Partition Equal Subset Sum.

解法三 - DP

前面的 memo[sum][curIdx] 存的是能否從 nums[0]-nums[curIdx] 的value 中選出一些數，這些數的和為 sum。所以現在就讓我們定義 dp[s][i] 為能否從 nums[0]-nums[i] 的value 中選出一些數，這些數的和為 s。

定義出子問題之後，下一步就是 recurrence formula，我們可以分成兩種情況來討論：

1. 包含 nums[i]: dp[s][i] = dp[s-nums[i]][i-1]

2. 不包含 nums[i]: dp[s][i] = dp[s][i-1]

所以應該要寫成 dp[s][i] = dp[s-nums[i]][i-1] || dp[s][i-1]。

初始化需要先初始化

1. 第一個 row：s == 0 時，所有的都是 true

2. 第一個 column: 只能用第一個 element 時，只有 s == nums[0] 才是 true

實作出來的程式碼如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum=0;

        for(auto n: nums)
            sum += n;

        // If sum is odd, it's impossible to have two subsets with equal sum
        if(sum % 2 != 0)
            return false;

        // Start building dp table bottom-up
        int n = nums.size();
        vector<vector<bool>> dp(sum/2+1, vector<bool>(n));

        // Init
        for(int i=0; i<n; i++)
            dp[0][i] = true;

        for(int s=0; s<=sum/2; s++)
            dp[s][0] = (s == nums[0]) ? true : false;

        // DP
        for(int s=1; s<=sum/2; s++) {
            for(int i=1; i<n; i++) {
                dp[s][i] = (nums[i] <= s ? dp[s-nums[i]][i-1] : false) || dp[s][i-1];
            }
        }

        return dp[sum/2][nums.size()-1];
    }
};