前言

今天繼續挑戰top 100 liked中sum相關的題目─416. Partition Equal Subset Sum，是不是感覺跟昨天的題目有點像呢？一起來解解看吧！

想法

先不論昨天的題目，看到這個問題的第一個想法就是把新的target算出來─這題的話就是加總/2，如果發現是奇數的話還可以先提前確認為false。而這題也是有多種想法可以進行：

DFS

不運用任何dp等等的方法可以直接用dfs的方式來爆開它，
(以下解法擷取自討論區)

class Solution {
public:
    bool backtrack(vector<int>& nums, int start, int target) {
        if (target <= 0) return target == 0;
        for (int i = start; i < nums.size(); i++) 
            if (backtrack(nums, i + 1, target - nums[i])) return true;
        return false;
    }
    
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        return !(sum & 1) && backtrack(nums, 0, sum >> 1);
    }
};

DP

而昨天剛掌握的DP作法肯定要來試一下的，邏輯也相同，只是更單純了，我們不需要計算有多少種組合，只要確定有就好了。
跟昨天不一樣的是今天我只用一維的DP來儲存，畢竟我也不在乎它是取幾個才能得到答案、最後有幾種組合，我只要中間有看到有解可行就夠了。
不過要注意的是在遍歷target的時候要從大開始往回檢查，因為從0開始會重複計算到自己剛剛的值，變成說現在nums有一個1，在檢查target的時候從0開始檢查，所以存入了pos[0+1]是可能的，等檢查到target=1的時候又發現pos[1]是有可能的，又把pos[1+1]也設為可能...這樣就等於是把同一個數重複使用了。
程式碼如下：

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        // compute the sum
        int sum = accumulate(nums.begin() , nums.end() , 0);
        // target=sum/2
        if(sum%2!=0){
            return false;
        }
        int target = sum/2;
        // use dp[x] to search if sum=x is possible
        vector<int> pos(target+1,0);
        pos[0]=1;
        // from target to 0 to avoid compute itself repeatedly
        for(int i=0;i<nums.size();++i){
            for(int j=target;j>=0;--j){
                // if the sum is possible, add this number to that sum will ne possible
                if(pos[j]>0 && (j+nums[i])<=target){
                    pos[j+nums[i]]=1;
                }
                if(pos[target]>0){
                    return true;
                }
            }
        }
        return false;
    }
};

bitset

在討論區有很多bitset的解法，所以也來看一下是怎麼做的~

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        bitset<10001> bits(1);
        int sum = accumulate(nums.begin(), nums.end(), 0);
        for (auto n : nums) bits |= bits << n;
        return !(sum & 1) && bits[sum >> 1];
    }
};

其實這個解法就是把dp的那個vector變成bit組，而已！看它是在哪一位，就把那位左移nums[i]位，然後or，最後先檢查是否為奇數以及該位是否為1就好了！

結語

沒想到光是top 100 liked中sum相關的題目就這麼多~ 是不是能一直寫到day 30呢XD