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

質問する

コード#コード#

// dfs - Time Limit Exceeded

class Solution {
public:
    bool canPartition(vector<int>& nums) {
         int target = accumulate(nums.begin(), nums.end(), 0);
        
         if (target%2 == 1) return false;
         return recur(nums, 0, 0, target/2);
    }
    
    bool recur(vector<int>& v, int idx, int cur, int target){
        if (cur == target) return true;
        
        for (int i = idx; i < v.size(); i++){
            if (cur+v[i] <= target and recur(v, i+1, cur+v[i], target)) return true;
        }
        return false;
    }
};

// Accepted

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

に近づく