Skip to main content
Talentd

Minimum Operations to Form Subset Sum II - Solution & Explanation

Hard12 min read
Practice this problem

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, multiplication and division operations may be performed in any order.

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 = [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 2:

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

Output: 2

Explanation:​​​​​​​

  • Turn nums[1] = 3 into 2 using 2 operations:
    • Divide nums[1] to get 1.
    • Multiply nums[1] = 1 to get 2.
  • After these operations, nums = [6, 2]. The subset {6, 2} sums to 8 using 2 operations in total.

Example 3:

Input: nums = [2,2], sum = 7

Output: -1

Explanation:

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

 

Constraints:

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

Approach Overview

Problem Overview: You're given an array and a target sum. You need the minimum number of operations (insertions, deletions, or modifications depending on the exact statement) to make some subset of the array sum to the target. This is a variation of the classic subset sum problem, but instead of just checking feasibility, you're optimizing the cost to reach the target.

Approach 1: Brute Force - Enumerate All Subsets (O(2^n) time, O(n) space)

Generate every subset using recursion or bitmasks, compute the sum, and track the minimum operations needed to reach the target. This is only viable for n ≤ 20. It shows you understand the subset-sum structure, but it won't scale. Use it only as a sanity check for small test cases.

Approach 2: 0-1 Knapsack DP - Bottom-Up (O(n * target) time, O(target) space)

This is the optimal approach. Define dp[s] as the minimum operations needed to form sum s using the items processed so far. Initialize dp[0] = 0 and all other states to infinity. For each number num in the array, iterate s from target down to num and update dp[s] = min(dp[s], dp[s - num] + cost). The reverse iteration is critical — it ensures each number is used at most once, which is the defining property of 0-1 Knapsack. The answer is dp[target] if it's finite, otherwise -1.

Approach 3: 0-1 Knapsack DP - Top-Down with Memoization (O(n * target) time, O(n * target) space)

Use recursion with a memo table memo[i][s] representing the minimum operations to reach sum s using the first i items. At each step, either skip the current item or take it if it doesn't exceed the target. This approach is more intuitive for some people, but the space overhead is higher. Prefer it when you need to reconstruct the exact subset or when the recursive formulation is easier to reason about.

Recommended for interviews: Interviewers expect the bottom-up 0-1 Knapsack DP. The brute force shows you understand the problem, but the optimized DP demonstrates that you can recognize the classic dynamic programming pattern and apply it under constraints. Always start by stating the DP state and transition, then implement the space-optimized version. This problem is a direct application of the knapsack pattern, so mastering the 0-1 Knapsack template is the key to solving it quickly.

Solution

Unlike the previous problem, multiplications and divisions may be interleaved in any order. Notice that a multiplication immediately followed by a division is a no-op, since \lfloor 2x / 2 \rfloor = x, so any multiplication that happens before a division can be cancelled against it, wasting two operations. After repeatedly cancelling such pairs, every sequence reduces to "divide i times, then multiply j times", which turns x into \lfloor x / 2^i \rfloor times 2^j at a cost of i + j operations.

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 the number of divisions i and multiplications j to get the value y = \lfloor x / 2^i \rfloor times 2^j, and update f[w] with f[w - y] + i + j 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 M times log S), and the space complexity is O(S). Here, n and M are the length and the maximum value of the array nums, and S is the given sum.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force - Enumerate All SubsetsO(2^n)O(n)Only for n ≤ 20 or as a brute-force validator
0-1 Knapsack DP - Bottom-UpO(n * target)O(target)General case; optimal for most constraints
0-1 Knapsack DP - Top-Down MemoizationO(n * target)O(n * target)When you need to reconstruct the subset or prefer recursion

Video Solution

Super Hard💀Math + DP DSA Question asked by Leetcode in Weekly Contest 517(Q4,4041) • Kumar K [Amazon] • 682 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Minimum Operations to Form Subset Sum II easy or hard?
It's rated Hard on FleetCode with a 47.4% acceptance rate. The difficulty comes from recognizing that it's a 0-1 Knapsack variant and correctly handling the cost minimization. Once you identify the DP state, the implementation is straightforward.
Minimum Operations to Form Subset Sum II Python/Java solution
In Python, use a list dp = [float('inf')] * (target + 1) and update it with a reverse loop. In Java, use int[] dp = new int[target + 1] filled with Integer.MAX_VALUE. Both follow the same 0-1 Knapsack transition: dp[s] = min(dp[s], dp[s - num] + cost).
How to solve Minimum Operations to Form Subset Sum II in O(n * target)?
Use a 1D DP array where dp[s] stores the minimum operations to form sum s. Initialize dp[0] = 0 and the rest to infinity. For each number, iterate s from target down to num and update dp[s] = min(dp[s], dp[s - num] + cost). The reverse iteration enforces the 0-1 property.
What is the best approach for Minimum Operations to Form Subset Sum II?
The best approach is bottom-up 0-1 Knapsack dynamic programming. It runs in O(n * target) time and O(target) space, which is optimal for this problem. The key is to iterate the sum backwards so each element is used at most once.
Is Minimum Operations to Form Subset Sum II asked at Google/Amazon/Meta?
Subset sum and knapsack-style DP problems are frequently asked at Google, Amazon, and Meta. This specific problem is a hard variation that tests your ability to combine DP with cost minimization, so it's a strong interview prep question for those companies.
What data structure is used in Minimum Operations to Form Subset Sum II?
The solution uses a 1D dynamic programming array (or a 2D memo table for the top-down approach). No complex data structures are required — the core is the DP state transition that tracks the minimum cost to reach each sum.
What is the time complexity of Minimum Operations to Form Subset Sum II?
The optimal 0-1 Knapsack DP solution runs in O(n * target) time, where n is the number of elements and target is the required subset sum. The space complexity is O(target) for the bottom-up version, or O(n * target) for the top-down memoized version.

Ready to solve this problem?

Practice Minimum Operations to Form Subset Sum II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Minimum Operations to Form Subset Sum I