Recursive DP solution using memoization in C++

programming
Tags: #<Tag:0x00007f18268a5710>

#1
bool knapsack(vector<int> &nums, int idx, int target_sum, vector<vector<int>> &memo)
    if(idx==nums.size() && target_sum!=0)
        return 0;

    if(target_sum<0)
        return 0;
    
    if(target_sum==0)
        return 1;
    
    if(memo[target_sum][idx] != -1)
        return (bool)memo[target_sum][idx];
    
    bool with_val = knapsack(nums, idx+1, target_sum-nums[idx], memo);
    bool without_val = knapsack(nums, idx+1, target_sum, memo);
    memo[target_sum][idx] = (int)(with_val || without_val);
    
    return (bool)memo[target_sum][idx];
}

int Solution::solve(vector<int> &A, int B) {
    if(A.empty())
        return 0;
    vector<vector<int>> memo (B+1, vector<int>(A.size(), -1));
    return knapsack(A, 0, B, memo);
}