4040. Minimum Operations to Form Subset Sum I

You are given an integer array nums and an integer sum.

In one operation, choose an element with current value x and replace it with either 2 * x or floor(x / 2).

For each element, all multiplication operations performed on it must occur before any division operations performed on it.

Return the minimum number of operations needed so that some subset of the resulting array has a sum exactly equal to sum. If it is impossible, return -1.

The floor() function returns the integer part of the division.

class Solution {
public:
    int minOperations(vector<int>& nums, int sum) {
        vector<long long> dp(sum + 1, INT_MAX);
        dp[0] = 0;
        for(auto& n : nums) {
            unordered_map<int,int> cost;
            for(int val = n, c = 0; val <= sum; val *= 2, c++) {
                cost[val] = c;
            }
            for(int val = n, c = 0; val; val /= 2, c++) {
                cost[val] = c;
            }
            vector<long long> dpp = dp;
            for(auto& [k,v] : cost) {
                for(int s = sum; s >= k; s--) {
                    dpp[s] = min(dpp[s], dp[s-k] + v);
                }
            }
            swap(dp,dpp);
        }
        return dp[sum] == INT_MAX ? -1 : dp[sum];
    }
};