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

• 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);
}

};
``````

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