# C++ Simple DP & DFS

• ``````// O(2*sum*n) DP
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (target < -sum || target > sum)
return 0;
vector<int> dp(sum * 2 + 1), next_dp(sum * 2 + 1);
dp[sum] = 1;
for (int i = 1; i <= nums.size(); ++ i)
{
for (int j = sum; j >= -sum; -- j)
{
int idx = j + sum;
if (idx - nums[i - 1] >= 0)
next_dp[idx] = dp[idx - nums[i - 1]];
if (idx + nums[i - 1] < sum * 2 + 1)
next_dp[idx] += dp[idx + nums[i - 1]];
}
swap(dp, next_dp);
}
return dp[target + sum];
}
};
``````
``````//O(2^n) DFS
class Solution {
int solve(vector<int> const & nums, int target, int k)
{
if (k < 0)
return target == 0;
return solve (nums, target - nums[k], k - 1) + solve (nums, target + nums[k], k - 1);
}
public:
int findTargetSumWays(vector<int> const & nums, int target) {
return solve(nums, target, (int)nums.size() - 1);
}
};
``````

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