Untitled

// AMAN JAIN MCA 2nd year

class Solution {
public:

    int getMin(vector<int>& nums, vector<vector<int>>& dp, int x, int left, int right, int totalOperations) {
        if(x == 0) {
            return totalOperations;
        }
        else if(left > right) {
            return -1;
        }
        else if(dp[left][right] != -2) {
            return dp[left][right];
        }
        else {
            int leftSubtree = -1, rightSubtree = -1;
            if(x - nums[left] >= 0) {
                leftSubtree = getMin(nums, dp, x - nums[left], left + 1, right, totalOperations + 1);
            }
            if(x - nums[right] >= 0) {
                rightSubtree = getMin(nums, dp, x - nums[right], left, right - 1, totalOperations + 1);
            }
            if(leftSubtree == -1 && rightSubtree == -1) {
                dp[left][right] = -1;
                return dp[left][right];
            }
            else if(leftSubtree == -1 || rightSubtree == -1) {
                dp[left][right] = leftSubtree == -1 ? rightSubtree : leftSubtree;
                return dp[left][right];
            }
            else {
                dp[left][right] = min(leftSubtree, rightSubtree);
                return dp[left][right];
            }
        }
    }

    int minOperations(vector<int>& nums, int x) {
        int N = nums.size(), totalOperations = 0, left = 0, right = N - 1;
        vector<vector<int>> dp(N, vector<int>(N, -2));
        return getMin(nums, dp, x, left, right, totalOperations);
    }
};