[Day 24] Leetcode 416. Partition Equal Subset Sum (C++)

前言

今天继续挑战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