Minimum Operations to Form Subset Sum I | Leetcode 4040

class Solution {
    int minCount(vector<int>& nums,int idx,int sum,vector<vector<int>>& min_ops){
        if(sum==0)
            return 0;
        if(idx>=nums.size() or sum<0)
            return INT_MAX;
        if(min_ops[idx][sum]!=-1)
            return min_ops[idx][sum];
        
        // Don't Include curr element
        int ops = minCount(nums,idx+1,sum,min_ops);

        // Include cases
        int curr = nums[idx];
        int op_count = 0;
        int result;

        // Multiplication
        while(curr<=sum){
            result = minCount(nums,idx+1,sum-curr,min_ops);
            if(result!=INT_MAX)
                ops = min(ops,result + op_count);
            curr *= 2;
            op_count++;
        }
        // Division
        op_count = 0;
        curr = nums[idx];
        while(curr>=1){
            result = minCount(nums,idx+1,sum-curr,min_ops);
            if(result!=INT_MAX)
                ops = min(ops,result + op_count);
            curr /= 2;
            op_count++;
        }
        return min_ops[idx][sum] = ops;
    }
public:
    int minOperations(vector<int>& nums, int sum) {
        int n=nums.size();
        vector<vector<int>> min_ops(n,vector<int>(sum+1,-1));

        int result = minCount(nums,0,sum,min_ops);
        return result==INT_MAX? -1 : result;
    }
};
/*
//JAVA
```java
import java.util.*;

class Solution {
    private static final int INF = Integer.MAX_VALUE;

    private int minCount(int[] nums, int idx, int sum, int[][] minOps) {
        if (sum == 0)
            return 0;

        if (idx >= nums.length || sum < 0)
            return INF;

        if (minOps[idx][sum] != -1)
            return minOps[idx][sum];

        // Don't include current element
        int ops = minCount(nums, idx + 1, sum, minOps);

        // Include cases
        int curr = nums[idx];
        int opCount = 0;

        // Multiplication
        while (curr <= sum) {
            int result = minCount(nums, idx + 1, sum - curr, minOps);

            if (result != INF)
                ops = Math.min(ops, result + opCount);

            curr *= 2;
            opCount++;
        }

        // Division
        opCount = 0;
        curr = nums[idx];

        while (curr >= 1) {
            int result = minCount(nums, idx + 1, sum - curr, minOps);

            if (result != INF)
                ops = Math.min(ops, result + opCount);

            curr /= 2;
            opCount++;
        }

        return minOps[idx][sum] = ops;
    }

    public int minOperations(int[] nums, int sum) {
        int n = nums.length;

        int[][] minOps = new int[n][sum + 1];

        for (int[] row : minOps)
            Arrays.fill(row, -1);

        int result = minCount(nums, 0, sum, minOps);

        return result == INF ? -1 : result;
    }
}
```

#Python
```python
class Solution:
    INF = float("inf")

    def minCount(self, nums, idx, target, min_ops):
        if target == 0:
            return 0

        if idx >= len(nums) or target < 0:
            return self.INF

        if min_ops[idx][target] != -1:
            return min_ops[idx][target]

        # Don't include current element
        ops = self.minCount(nums, idx + 1, target, min_ops)

        # Include cases
        curr = nums[idx]
        op_count = 0

        # Multiplication
        while curr <= target:
            result = self.minCount(
                nums, idx + 1, target - curr, min_ops
            )

            if result != self.INF:
                ops = min(ops, result + op_count)

            curr *= 2
            op_count += 1

        # Division
        op_count = 0
        curr = nums[idx]

        while curr >= 1:
            result = self.minCount(
                nums, idx + 1, target - curr, min_ops
            )

            if result != self.INF:
                ops = min(ops, result + op_count)

            curr //= 2
            op_count += 1

        min_ops[idx][target] = ops
        return ops

    def minOperations(self, nums, sum):
        n = len(nums)

        min_ops = [[-1] * (sum + 1) for _ in range(n)]

        result = self.minCount(nums, 0, sum, min_ops)

        return -1 if result == self.INF else result
```
*/