C++ DFS+MEMORIZATION


  • 1
    B
    class Solution {
        int helper(vector<int>& nums, int start, int target, vector<vector<int>> &m) {
            if(target == 0 && start == nums.size()) return 1;
            if(target > 1000 || target < -1000 || start == nums.size()) return 0;
            if(m[start][target+1000]!=-1) return m[start][target+1000];
            int res = helper(nums,start+1,target-nums[start],m) + helper(nums,start+1,target+nums[start], m);
            m[start][target+1000]=res;
            return res;
        }
    public:
        int findTargetSumWays(vector<int>& nums, int S) {
            vector<vector<int>> m(21, vector<int>(2001,-1));
            return helper(nums, 0, S, m);
        }
    };
    

Log in to reply
 

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