Untitled
class Solution { int count = 0; vector<string> v; public: void solve(string s, int ind, int sum, vector<vector<int>>& dp, vector<int>& nums, int k){ if(ind == nums.size()) {v.push_back(s); return;} // 1st Case: Positive int modifiedSum = sum + nums[ind]; s += ("+" + to_string(nums[ind])); // if(modifiedSum == k){ // count++; // } if(dp[ind][modifiedSum] == 0){ count++; } else{ dp[ind][modifiedSum]++; } solve(s, ind + 1, modifiedSum, dp, nums, k); int j = s.size()-1; while(j >= 0 && (s[j] != '-' && s[j] != '+')){ j--; } s = s.substr(0, j); // 2nd Case: Negative modifiedSum = sum - nums[ind]; s += ("-" + to_string(nums[ind])); // if(modifiedSum == k){ // count++; // } if(dp[ind][modifiedSum] != 0){ count++; } else{ dp[ind][modifiedSum]++; } solve(s, ind + 1, modifiedSum, dp, nums, k); j = s.size()-1; while(j >= 0 && (s[j] != '-' && s[j] != '+')){ j--; } s = s.substr(0, j); } int findTargetSumWays(vector<int>& nums, int target) { int posSum = 0; for(auto x : nums){ posSum += x; } vector<vector<int>> dp(nums.size() + 1, vector<int> (2*posSum+1, 0)); solve("", 0, 0, dp, nums, target); // for(auto x : v){ // cout<<x<<endl; // } return count; } };
Leave a Comment