2143. Choose Numbers From Two Arrays in Range

You are given two 0-indexed integer arrays nums1 and nums2 of length n.

A range [l, r] (inclusive) where 0 <= l <= r < n is balanced if:

• For every i in the range [l, r], you pick either nums1[i] or nums2[i].
• The sum of the numbers you pick from nums1 equals to the sum of the numbers you pick from nums2 (the sum is considered to be 0 if you pick no numbers from an array).

Two balanced ranges from [l1, r1] and [l2, r2] are considered to be different if at least one of the following is true:

• l1 != l2
• r1 != r2
• nums1[i] is picked in the first range, and nums2[i] is picked in the second range or vice versa for at least one i.

Return the number of different ranges that are balanced. Since the answer may be very large, return it modulo 109 + 7.

class Solution {
    int mod = 1e9 + 7, mid = 5000;
    int dp[100][10001];
    int helper(vector<int>& nums1, vector<int>& nums2, int p, int sum) {
        if(p == nums1.size() or sum < 0 or sum > 10000)
            return sum == mid;
        if(dp[p][sum] != -1) return dp[p][sum];
        dp[p][sum] = ((sum == mid) + helper(nums1, nums2, p + 1, sum + nums1[p]) + helper(nums1, nums2, p + 1, sum - nums2[p])) % mod;
        return dp[p][sum];
    }
public:
    int countSubranges(vector<int>& nums1, vector<int>& nums2) {
        memset(dp,-1,sizeof(dp));
        int res = 0;
        for(int i = 0; i < nums1.size(); i++) {
            res = (res + helper(nums1, nums2, i, mid) - 1) % mod;
        }
        return res;
    }
};