C++ two DP solutions with comments


  • 0

    (1) 16ms backtracking with memory.

    class Solution {
    private:
        unordered_map<int, unordered_map<int, bool>> visited;       // visited[end][target] records visited cases
        
        bool hasSum(vector<int>& nums, int end, int target) {       // end: search within nums[0 - end]; target: sum target
            if (end < 0 || target <= 0) { return target == 0; }     // base case
            
            if (visited.count(end) == 0 || visited[end].count(target) == 0) {
                visited[end][target] = hasSum(nums, end - 1, target - nums[end]) || hasSum(nums, end - 1, target);
            }
            return visited[end][target];
        }
    
    public:
        bool canPartition(vector<int>& nums) {
            int sum = 0;
            for (int n : nums) { sum += n; }                        // calculate array sum
            if (sum & 1 == 1) { return false; }                     // odd sum is impossible to partition
            
            return hasSum(nums, nums.size() - 1, sum / 2);          // search for answer
        }
    };
    

    (2) 96ms iterative DP. This one is much slower than above. I think the bottleneck is the target sum in DP - iterative solution needs to calculate every possible target sum and finally reach the halfSum we are looking for, but the backtracking way could skip lots of unnecessary target sum and thus much faster.

    bool canPartition(vector<int>& nums) {
            int sum = 0;
            for (int n : nums) { sum += n; }            // calculate array sum
            if (sum & 1 == 1) { return false; }         // odd sum is impossible to partition
            
            int halfSum = sum / 2;                      // halfSum is the target sum we are looking for
            bool hasSum[nums.size()][halfSum + 1];      // hasSum[end][target] records visited cases
            memset(hasSum, false, sizeof(hasSum));
            
            for (int end = 0; end < nums.size(); end++) {
                for (int target = 0; target <= halfSum; target++) {
                    hasSum[end][target] = end == 0 ? 
                                          target == 0 : 
                                          hasSum[end - 1][target] || (nums[end] <= target && hasSum[end - 1][target - nums[end]]);
                }
            }
            
            return hasSum[nums.size() - 1][halfSum];
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.