# Two C++ Solutions: DFS and DP

• 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'.

• You sure DFS is N^2 ?, for each n, you have a for loop, each sub-problem in the for loop will lead to another for loop recursively.

• This post is deleted!

• @vesion
Hi vesion, test cases for these problem was designed too weak. I'll add more test cases in minutes. Thanks for your feedback.

• @vesion
Hi, can you explain why DFS is N^2 ?
Thanks

• @zyoppy008
I'm so sorry for my wrong answer above on the time complexity of DFS solution.
It's time complexity is exponential, O(2^n) specifically. Because the progress is pretty much the same with the combination problem, so it is also exponential.

• @ywh1988
I'm so sorry for my wrong answer, it's O(2^n). Apologize again :)

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