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 {
        map<int,bool> dpcan;
        bool canPartitionHelper(const vector<int>& nums, const int & target, const int& left){
                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;
            dpcan[target] = result;
            return result;
        bool canPartition(vector<int>& nums) {
                return true;
            int sum = 0;
            for(int i:nums)
                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.