Partition Array into Two Equal Product Subsets - Solution & Explanation
Problem Statement
You are given an integer array nums containing distinct positive integers and an integer target.
Determine if you can partition nums into two non-empty disjoint subsets, with each element belonging to exactly one subset, such that the product of the elements in each subset is equal to target.
Return true if such a partition exists and false otherwise.
Example 1:
Input: nums = [3,1,6,8,4], target = 24
Output: true
Explanation: The subsets [3, 8] and [1, 6, 4] each have a product of 24. Hence, the output is true.
Example 2:
Input: nums = [2,5,3,7], target = 15
Output: false
Explanation: There is no way to partition nums into two non-empty disjoint subsets such that both subsets have a product of 15. Hence, the output is false.
Constraints:
3 <= nums.length <= 121 <= target <= 10151 <= nums[i] <= 100- All elements of
numsare distinct.
Approach Overview
Problem Overview: You are given an integer array and must determine whether it can be partitioned into two non‑empty subsets whose products are equal. Every element must belong to exactly one of the two groups. The core challenge is exploring different subset combinations while comparing their products.
Approach 1: Recursive Subset Enumeration (Backtracking) (Time: O(2^n), Space: O(n))
This approach generates all possible subsets using recursion. At each index you decide whether to include the current element in subset A or subset B. Track the running product of subset A while the product of subset B can be derived from the remaining elements. If at any point both subsets become non‑empty and their products match, you return true. The key idea is exhaustive exploration of every partition configuration. Recursion depth is at most n, so the stack space is O(n), while the number of states explored is O(2^n).
Approach 2: Binary Enumeration with Bit Masks (Time: O(2^n * n), Space: O(1))
Binary enumeration treats each subset as a bitmask where the i-th bit indicates whether nums[i] belongs to the first subset. Iterate from 1 to (1 << n) - 1 and compute the product of elements selected by the mask. The remaining elements implicitly form the second subset. If both subsets are non‑empty and their products match, the partition exists. This approach relies on bit manipulation to efficiently enumerate subsets and is often easier to implement than recursion. Each mask requires scanning up to n elements to compute the subset product, resulting in O(2^n * n) time.
One useful observation: if the total product of the array is P, the product of one subset must be sqrt(P) for the two subsets to match. During enumeration you can stop early if the running product exceeds this target or if P is not a perfect square. This pruning reduces unnecessary checks but does not change the worst‑case complexity.
The algorithm relies heavily on systematic subset generation, which is a common technique in problems involving arrays and exhaustive search. Bitmask enumeration is particularly effective when n is small (typically ≤ 20), since every subset can be explored within manageable time.
Recommended for interviews: Binary enumeration with bit masks. Interviewers expect you to recognize that the problem requires exploring all subset partitions and that bitmasks provide a compact, iterative way to generate them. Mentioning the recursive brute force first demonstrates problem‑solving intuition, while implementing the bitmask approach shows strong familiarity with subset enumeration patterns.
Solution
We can use binary enumeration to check all possible subset partitions. For each subset partition, we can calculate the product of the two subsets and check whether both are equal to the target value.
Specifically, we can use an integer i to represent the state of the subset partition, where the binary bits of i indicate whether each element belongs to the first subset. For each possible i, we calculate the product of the two subsets and check whether both are equal to the target value.
The time complexity is O(2^n times n), where n is the length of the array. The space complexity is O(1).
Code
Python
Java
C++
Go
TypeScript
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Subset Enumeration (Backtracking) | O(2^n) | O(n) | Useful when explaining brute force reasoning or when recursion is preferred for exploring partitions |
| Binary Enumeration (Bitmask) | O(2^n * n) | O(1) | Practical approach for small arrays; simple implementation using bit operations |
| Binary Enumeration with Product Pruning | O(2^n * n) | O(1) | When the total product allows early pruning (e.g., target product sqrt(P)) to skip unnecessary subset checks |
Video Solution
3566. Partition Array into Two Equal Product Subsets | Weekly 452 | 1st Problem • Tech Courses • 863 views views
Watch 8 more video solutions →Frequently Asked Questions
Is Partition Array into Two Equal Product Subsets easy or hard?
Partition Array into Two Equal Product Subsets Python/Java solution
How to solve Partition Array into Two Equal Product Subsets in O(n)?
What is the best approach for Partition Array into Two Equal Product Subsets?
Is Partition Array into Two Equal Product Subsets asked at Google/Amazon/Meta?
What data structure is used in Partition Array into Two Equal Product Subsets?
What is the time complexity of Partition Array into Two Equal Product Subsets?
Ready to solve this problem?
Practice Partition Array into Two Equal Product Subsets with our built-in code editor and test cases.
Practice on FleetCode