6ms explained C++ solution beating 96% using combination sum and DP


  • 0

    This question comes to me after I have finished combination sum and DP optimization.
    First, to be aware of is that this question can be transform into combination sum by saying it should return true if a subset of the list can made a certain sum.
    Second, to store the result and avoid recompute, we can use a map.
    So here is the solution.

    class Solution {
    public:
        map<int,bool> dpcan;
        bool canPartitionHelper(const vector<int>& nums, const int & target, const int& left){
            if(dpcan.find(target)!=dpcan.end())
                return dpcan[target];
            bool result = false;
            for(int i = left;i<nums.size();++i){
                if(nums[i] == target ||
                   (nums[i]<target && canPartitionHelper(nums, target-nums[i], i+1))){
                    result = true;
                    break;
                }
            }
            dpcan[target] = result;
            return result;
        }
        bool canPartition(vector<int>& nums) {
            if(nums.size()==0)
                return true;
            int sum = 0;
            for(int i:nums)
                sum+=i;
            if(sum%2!=0)
                return false;
            return canPartitionHelper(nums, sum/2, 0);
        }
    
    };
    

Log in to reply
 

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