Partition Array into Two Equal Product Subsets solution and explanation
7 more videos on this problem
3566. Partition Array into Two Equal Product Subsets | Weekly 452 | 1st ProblemTech Courses · 6:38 · 863 views
Partition Array into Two Equal Product Subsets | Weekly Contest 452 | Java | Developer CoderDeveloper Coder · 10:42 · 818 views
3566. Partition Array into Two Equal Product Subsets | Weekly Contest 452 | LeetcodeRapid Syntax · 11:06 · 656 views
3566. Partition Array into Two Equal Product Subsets (Leetcode Medium)Programming Live with Larry · 6:08 · 455 views
Leetcode Weekly Contest 452 - Q1. Partition Array into Two Equal Product SubsetsADevOpsEngineer · 8:24 · 374 views
LeetCode 3566. Partition Array into Two Equal Product Subsets | Subset | BitmaskingLeet's Code · 19:18 · 357 views
Q1. Partition Array into Two Equal Product Subsets| POTD | DFS | Contest #452 | TechTalesTechTales by Anisha · 13:10 · 276 views
Focus Mode: LeetCode 3566 Partition Array into Two Equal Product Subsets + Bin Tere | Coding Vlog 🎧💻Chillhbe · 7:19 · 30 views
The problem
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).
class Solution:
def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
n = len(nums)
for i in range(1 << n):
x = y = 1
for j in range(n):
if i >> j & 1:
x *= nums[j]
else:
y *= nums[j]
if x == target and y == target:
return True
return Falseclass Solution {
public boolean checkEqualPartitions(int[] nums, long target) {
int n = nums.length;
for (int i = 0; i < 1 << n; ++i) {
long x = 1, y = 1;
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) {
x *= nums[j];
} else {
y *= nums[j];
}
}
if (x == target && y == target) {
return true;
}
}
return false;
}
}class Solution {
public:
bool checkEqualPartitions(vector<int>& nums, long long target) {
int n = nums.size();
for (int i = 0; i < 1 << n; ++i) {
long long x = 1, y = 1;
for (int j = 0; j < n; ++j) {
if ((i >> j & 1) == 1) {
x *= nums[j];
} else {
y *= nums[j];
}
if (x > target || y > target) {
break;
}
}
if (x == target && y == target) {
return true;
}
}
return false;
}
};function checkEqualPartitions(nums: number[], target: number): boolean {
const n = nums.length;
for (let i = 0; i < 1 << n; ++i) {
let [x, y] = [1, 1];
for (let j = 0; j < n; ++j) {
if (((i >> j) & 1) === 1) {
x *= nums[j];
} else {
y *= nums[j];
}
if (x > target || y > target) {
break;
}
}
if (x === target && y === target) {
return true;
}
}
return false;
}func checkEqualPartitions(nums []int, target int64) bool {
n := len(nums)
for i := 0; i < 1<<n; i++ {
x, y := int64(1), int64(1)
for j, v := range nums {
if i>>j&1 == 1 {
x *= int64(v)
} else {
y *= int64(v)
}
if x > target || y > target {
break
}
}
if x == target && y == target {
return true
}
}
return false
}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 |
Frequently asked questions
Is Partition Array into Two Equal Product Subsets easy or hard?
The problem is typically classified as Medium because it requires recognizing the subset enumeration pattern and implementing it efficiently. The brute force idea is straightforward, but translating it into clean bitmask or recursive logic is the main challenge.
Partition Array into Two Equal Product Subsets Python/Java solution
Most implementations iterate through all subset masks and compute the product of selected elements. The same algorithm works across Python, Java, C++, Go, and TypeScript since it only relies on loops, multiplication, and bit operations.
How to solve Partition Array into Two Equal Product Subsets in O(n)?
An O(n) solution generally does not exist because the problem requires evaluating many possible partitions of the array. The common strategy is subset enumeration using recursion or bit masks, which runs in O(2^n) or O(2^n * n) time depending on implementation.
What is the best approach for Partition Array into Two Equal Product Subsets?
Binary enumeration using bit masks is the most practical approach. Each subset is represented as a bitmask and you iterate through all masks from 1 to (1<<n)-1. For each mask compute the subset product and compare it with the product of remaining elements. The method runs in O(2^n * n) time and works well when the array size is small.
Is Partition Array into Two Equal Product Subsets asked at Google/Amazon/Meta?
Subset enumeration and partition problems frequently appear in interviews at companies like Google, Amazon, and Meta. While the exact problem may vary, the core idea of generating subsets with bit masks or recursion is a standard interview pattern.
What data structure is used in Partition Array into Two Equal Product Subsets?
The problem primarily uses arrays combined with bit manipulation or recursion for subset generation. A bitmask integer is often used to represent whether each element belongs to a subset during enumeration.
What is the time complexity of Partition Array into Two Equal Product Subsets?
The typical solution explores all subsets, giving O(2^n * n) time complexity when using bitmask enumeration because each mask may require scanning n elements. Space complexity is O(1) for the iterative bitmask approach or O(n) when using recursive backtracking due to the recursion stack.