# 416 - Partition Equal Subset Sum

## 解法一 - 暴力法 (Recursive function)

``````class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;

for(auto n: nums)
sum += n;

// If sum is odd, it's impossible to have two subsets with equal sum
if(sum % 2 != 0)
return false;

return recursivePartition(nums, sum/2, 0);
}

private:
bool recursivePartition(vector<int>& nums, int sum, int curIdx) {
if(sum == 0)
return true;

if(nums.size() == 0 || curIdx >= nums.size())
return false;

// Use the value of curIdx
if(nums[curIdx] <= sum) {
if(recursivePartition(nums, sum-nums[curIdx], curIdx+1))
return true;
}

// Don't use the value of curIdx
return recursivePartition(nums, sum, curIdx+1);
}
};
``````

## 解法二 - Recursive + Memoization

``````class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;

for(auto n: nums)
sum += n;

// If sum is odd, it's impossible to have two subsets with equal sum
if(sum % 2 != 0)
return false;

vector<vector<int>> memo(sum/2+1, vector<int>(nums.size(), -1));

return recursivePartition(nums, sum/2, 0, memo);
}

private:
bool recursivePartition(vector<int>& nums, int sum, int curIdx, vector<vector<int>>& memo) {
if(sum == 0) {
return true;
}

if(nums.empty() || curIdx >= nums.size())
return false;

if(memo[sum][curIdx] == -1) {
if(nums[curIdx] <= sum) {
// Use the value of curIdx
if(recursivePartition(nums, sum-nums[curIdx], curIdx+1, memo)) {
memo[sum][curIdx] = 1;
return true;
}
}

// Don't use the value of curIdx
memo[sum][curIdx] = recursivePartition(nums, sum, curIdx+1, memo) ? 1 : 0;
}

return memo[sum][curIdx] == 1 ? true : false;
}
};
``````

Runtime: 40 ms, faster than 72.06% of C++ online submissions for Partition Equal Subset Sum. Memory Usage: 69.3 MB, less than 5.88% of C++ online submissions for Partition Equal Subset Sum.

## 解法三 - DP

1. 包含 nums[i]: `dp[s][i] = dp[s-nums[i]][i-1]`
2. 不包含 nums[i]: `dp[s][i] = dp[s][i-1]`

1. 第一個 row：s == 0 時，所有的都是 true
2. 第一個 column: 只能用第一個 element 時，只有 s == nums[0] 才是 true

``````class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum=0;

for(auto n: nums)
sum += n;

// If sum is odd, it's impossible to have two subsets with equal sum
if(sum % 2 != 0)
return false;

// Start building dp table bottom-up
int n = nums.size();
vector<vector<bool>> dp(sum/2+1, vector<bool>(n));

// Init
for(int i=0; i<n; i++)
dp[0][i] = true;

for(int s=0; s<=sum/2; s++)
dp[s][0] = (s == nums[0]) ? true : false;

// DP
for(int s=1; s<=sum/2; s++) {
for(int i=1; i<n; i++) {
dp[s][i] = (nums[i] <= s ? dp[s-nums[i]][i-1] : false) || dp[s][i-1];
}
}

return dp[sum/2][nums.size()-1];
}
};
``````