Minimum Operations to Form Subset Sum I - Solution & Explanation

Medium9 min read

Problem Statement

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.

Example 1:

Input: nums = [5,6,10], sum = 4

Output: 3

Explanation:

Divide nums[0] = 5 twice: 5 → 2 → 1, costing 2 operations.
Divide nums[1] = 6 once: 6 → 3, costing 1 operation.
After these operations, nums = [1, 3, 10]. The subset {1, 3} sums to 4 using 3 operations in total.

Example 2:

Input: nums = [10,2], sum = 13

Output: 3

Explanation:

Divide nums[0] = 10 once: 10 → 5, costing 1 operation.
Multiply nums[1] = 2 twice: 2 → 4 → 8, costing 2 operations.
After these operations, nums = [5, 8]. The subset {5, 8} sums to 13 using 3 operations in total.

Example 3:

Input: nums = [6,3], sum = 8

Output: -1

Explanation:

No sequence of operations lets a subset of nums sum to 8, so the answer is -1.

Constraints:

1 <= nums.length <= 100
1 <= nums[i] <= 500
1 <= sum <= 5000

Solution

Applying a multiplications followed by b divisions to an element gives \lfloor x times 2^a / 2^b \rfloor, which is exactly x times 2^{a-b} or \lfloor x / 2^{b-a} \rfloor. The same value is reachable with only |a - b| operations instead of a + b, so mixing the two directions is never worthwhile. Therefore each element has only two families of reachable values: x times 2^i or \lfloor x / 2^i \rfloor, each costing i operations, while an element left out of the subset costs nothing.

This turns the problem into a 0-1 knapsack: every element contributes at most one (value, cost) pair, and we want the minimum cost to fill a capacity of exactly sum.

We define f[w] as the minimum number of operations needed for a subset to sum to exactly w, with f[0] = 0 and all other entries set to +infty. For each element x, we iterate the capacity w from large to small, enumerate every value y that x can become together with its cost i, and update f[w] with f[w - y] + i whenever y leq w. If f[sum] is still +infty at the end, no valid sequence of operations exists and we return -1; otherwise we return f[sum].

The time complexity is O(n times S times log S), and the space complexity is O(S). Here, n is the length of the array nums, and S is the given sum.