C++ two DP solutions with comments

• (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];
}
``````

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