Skip to main content
Talentd

Minimum Operations to Form Subset Sum I - Solution & Explanation

MediumArrayDynamic Programming11 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, 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

Approach Overview

Problem Overview: You are given an array of positive integers and a target sum. The task is to pick the fewest elements from the array so that the selected elements sum exactly to the target. Since each element can be used at most once, this is the 0/1 subset-sum variant, not an unlimited coin-change problem.

Approach 1: Brute-Force Subset Enumeration (O(2^n) time, O(n) recursion stack)

Enumerate every subset of the array with a DFS choose/skip recursion. For each subset, compute its sum and the number of selected elements; whenever the sum matches the target, update the minimum count. This works only when n is very small, because the number of subsets is 2^n. It is still useful as a baseline to verify the DP results on small cases.

Approach 2: Top-Down Memoized DP (O(n * target) time, O(n * target) space)

Use dfs(i, remaining) to represent the minimum number of elements needed starting at index i to make remaining. At each step, either skip the current element or take it: dfs(i, remaining) = min(dfs(i + 1, remaining), 1 + dfs(i + 1, remaining - nums[i])). Cache results on the state (i, remaining) to avoid rework. This is the same 0/1 knapsack recurrence as the iterative version and is an acceptable interview solution if you want to explain recursion first.

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

Maintain a one-dimensional array dp[s] that stores the minimum number of selected elements required to make sum s. Initialize dp[0] = 0 and every other entry to INF. For each number num, update the array from target down to num using dp[s] = min(dp[s], dp[s - num] + 1). The reverse iteration is the key: it guarantees num is used at most once, exactly like a 0/1 knapsack item. If dp[target] is still INF, no subset sums to the target and you return -1.

Recommended for interviews: Start with the brute-force choose/skip explanation to show you understand the subset structure, then implement the bottom-up 0/1 knapsack solution. The top-down memoized DP is correct, but the bottom-up version removes the recursion stack and stores only O(target) state. This problem is a direct application of dynamic programming and 0/1 knapsack techniques. Practicing the descending-loop pattern on arrays makes these subset-sum questions much easier to recognize during interviews.

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute-force subset enumerationO(2^n)O(n)Only for small arrays or as a correctness baseline
Top-down memoized DPO(n * target)O(n * target)When you want a clean recursive explanation and the state table is manageable
Bottom-up 0/1 knapsackO(n * target)O(target)Best general-case answer; uses the least space and maps directly to 0/1 knapsack

Video Solutions (10)

Super Hard💀Dynamic Programming DSA Question asked by Leetcode in Weekly Contest 517(Q3,4040)

Kumar K [Amazon]44:113K views
Video 1 of 10

Frequently Asked Questions

Is Minimum Operations to Form Subset Sum I easy or hard?
It is a Medium problem. The main difficulty is recognizing the 0/1 knapsack structure and setting up the INF sentinel correctly; once you see that, the implementation is short and follows the standard subset-sum pattern.
Minimum Operations to Form Subset Sum I Python/Java solution?
In Python: dp = [INF] * (target + 1); dp[0] = 0; for x in nums: for s in range(target, x - 1, -1): dp[s] = min(dp[s], dp[s - x] + 1). Java and C++ use the same recurrence with an int array and a descending for-loop.
What is the best approach for Minimum Operations to Form Subset Sum I?
Bottom-up 0/1 knapsack DP is the best approach. It tracks the minimum number of selected elements for every sum up to the target in one pass, runs in O(n * target) time, and uses O(target) space. Brute force with O(2^n) time is only acceptable for tiny arrays.
Is Minimum Operations to Form Subset Sum I asked at Google/Amazon/Meta?
Subset-sum style 0/1 knapsack questions appear regularly in Google, Amazon, and Meta interviews. This exact statement may not be used verbatim, but the same choose/skip DP pattern is frequently tested and is important to master.
What data structure is used in Minimum Operations to Form Subset Sum I?
A one-dimensional integer array is the main data structure. dp[s] stores the minimum number of chosen elements required to form sum s, with dp[0] = 0 and all other entries initialized to a large INF value.
What is the time complexity of Minimum Operations to Form Subset Sum I?
The optimal 0/1 knapsack solution runs in O(n * target) time, where n is the number of array elements and target is the required subset sum. It uses O(target) space because the DP table is reduced to a single one-dimensional array.
How to solve Minimum Operations to Form Subset Sum I in O(n * target) time?
Initialize dp[0] = 0 and dp[1...target] = INF. For each number x in nums, loop s from target down to x and update dp[s] = min(dp[s], dp[s - x] + 1). The descending loop keeps every element used at most once. If dp[target] is INF, no subset sum exists, so return -1.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Minimum Operations to Form Subset Sum II