Solution 1 : DFS, O(2^N), TLE now due to new test cases added

```
class Solution {
public:
bool dfs(vector<int>& nums, int cur, int sum) {
if (sum == 0) return true;
if (sum < 0) return false;
for (int i = cur; i < (int)nums.size(); ++i)
if (dfs(nums, i+1, sum-nums[i])) return true;
return false;
}
bool canPartition(vector<int>& nums) {
long long sum = accumulate(nums.begin(), nums.end(), 0);
return sum & 1 ? false : dfs(nums, 0, sum/2);
}
};
```

Solution 2 : DP, O(M*N) (M is half of array sum), 251ms

```
class Solution {
public:
bool canPartition(vector<int>& nums) {
long long sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;
sum /= 2;
vector<int> dp(sum+1, 0);
for (int i = 1; i <= sum; ++i) dp[i] = INT_MIN;
for (int i = 0; i < (int)nums.size(); ++i) {
for (int j = sum; j >= nums[i]; --j)
dp[j] = max(dp[j-nums[i]]+1, dp[j]);
}
return dp[sum] > 0;
}
};
```

BTW, DP solution can be seen as the variation of the well-known '01 Knapsack Problem'.