3566: Partition Array into Two Equal Product Subsets
Problem Statement
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 such that the product of the elements in each subset equals the target.
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.Example 2
Input: nums = [2,5,3,7], target = 15
Output: false
Explanation: No possible partition exists where both subsets have product 15.
Problem Link:
View on LeetCode ↗
Approach 1: Prime Factorization with Bitmasking
This approach uses prime factorization to handle large products efficiently and bitmasking to explore all possible subsets.
Algorithm Steps
- Factorize each number in the array and the target into their prime factors
- Check if the total product of all elements equals target squared
- Use bitmasking to iterate through all possible subsets
- For each subset, check if its prime factorization matches the target's
Prime Factorization Solution
class Solution {
public:
bool checkEqualPartitions(vector<int>& nums, long long target) {
int n = nums.size();
vector<int> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int nprimes = primes.size();
vector<vector<int>> fact(n, vector<int>(nprimes, 0));
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int j = 0; j < nprimes; j++) {
int p = primes[j];
while (num % p == 0) {
fact[i][j]++;
num /= p;
}
}
}
vector<int> target_expo(nprimes, 0);
long long temp = target;
for (int j = 0; j < nprimes; j++) {
int p = primes[j];
while (temp % p == 0) {
target_expo[j]++;
temp /= p;
}
}
if (temp != 1) {
return false;
}
vector<int> total_expo(nprimes, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < nprimes; j++) {
total_expo[j] += fact[i][j];
}
}
for (int j = 0; j < nprimes; j++) {
if (total_expo[j] != 2 * target_expo[j]) {
return false;
}
}
int full_mask = (1 << n);
int forbidden_mask = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > target) {
forbidden_mask |= (1 << i);
}
}
for (int mask = 1; mask < full_mask - 1; mask++) {
if (mask & forbidden_mask) {
continue;
}
vector<int> cur_expo(nprimes, 0);
bool exceeded = false;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
for (int j = 0; j < nprimes; j++) {
cur_expo[j] += fact[i][j];
if (cur_expo[j] > target_expo[j]) {
exceeded = true;
break;
}
}
if (exceeded) break;
}
}
if (exceeded) continue;
bool valid = true;
for (int j = 0; j < nprimes; j++) {
if (cur_expo[j] != target_expo[j]) {
valid = false;
break;
}
}
if (valid) {
return true;
}
}
return false;
}
};class Solution {
public boolean checkEqualPartitions(int[] nums, long target) {
int n = nums.length;
int[] primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int nprimes = primes.length;
int[][] fact = new int[n][nprimes];
for (int i = 0; i < n; i++) {
int num = nums[i];
for (int j = 0; j < nprimes; j++) {
int p = primes[j];
while (num % p == 0) {
fact[i][j]++;
num /= p;
}
}
}
int[] target_expo = new int[nprimes];
long temp = target;
for (int j = 0; j < nprimes; j++) {
int p = primes[j];
while (temp % p == 0) {
target_expo[j]++;
temp /= p;
}
}
if (temp != 1) {
return false;
}
int[] total_expo = new int[nprimes];
for (int i = 0; i < n; i++) {
for (int j = 0; j < nprimes; j++) {
total_expo[j] += fact[i][j];
}
}
for (int j = 0; j < nprimes; j++) {
if (total_expo[j] != 2 * target_expo[j]) {
return false;
}
}
int full_mask = (1 << n);
int forbidden_mask = 0;
for (int i = 0; i < n; i++) {
if (nums[i] > target) {
forbidden_mask |= (1 << i);
}
}
for (int mask = 1; mask < full_mask - 1; mask++) {
if ((mask & forbidden_mask) != 0) {
continue;
}
int[] cur_expo = new int[nprimes];
boolean exceeded = false;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
for (int j = 0; j < nprimes; j++) {
cur_expo[j] += fact[i][j];
if (cur_expo[j] > target_expo[j]) {
exceeded = true;
break;
}
}
if (exceeded) break;
}
}
if (exceeded) continue;
boolean valid = true;
for (int j = 0; j < nprimes; j++) {
if (cur_expo[j] != target_expo[j]) {
valid = false;
break;
}
}
if (valid) {
return true;
}
}
return false;
}
}class Solution:
def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
n = len(nums)
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]
nprimes = len(primes)
fact = [[0]*nprimes for _ in range(n)]
for i in range(n):
num = nums[i]
for j in range(nprimes):
p = primes[j]
while num % p == 0:
fact[i][j] += 1
num = num // p
target_expo = [0]*nprimes
temp = target
for j in range(nprimes):
p = primes[j]
while temp % p == 0:
target_expo[j] += 1
temp = temp // p
if temp != 1:
return False
total_expo = [0]*nprimes
for i in range(n):
for j in range(nprimes):
total_expo[j] += fact[i][j]
for j in range(nprimes):
if total_expo[j] != 2 * target_expo[j]:
return False
full_mask = 1 << n
forbidden_mask = 0
for i in range(n):
if nums[i] > target:
forbidden_mask |= (1 << i)
for mask in range(1, full_mask - 1):
if mask & forbidden_mask:
continue
cur_expo = [0]*nprimes
exceeded = False
for i in range(n):
if mask & (1 << i):
for j in range(nprimes):
cur_expo[j] += fact[i][j]
if cur_expo[j] > target_expo[j]:
exceeded = True
break
if exceeded:
break
if exceeded:
continue
valid = True
for j in range(nprimes):
if cur_expo[j] != target_expo[j]:
valid = False
break
if valid:
return True
return False
Optimization: Prime factorization allows handling large products without overflow, and bitmasking efficiently explores all subsets.
Approach 2: Backtracking with Pruning
This approach uses backtracking with pruning to find a subset with product equal to target.
Backtracking Solution
class Solution {
public:
bool checkEqualPartitions(vector<int>& nums, long long target) {
long long total = 1;
for (int num : nums) {
total *= num;
if (total > target * target) return false;
}
if (total != target * target) return false;
return backtrack(nums, 0, 1, target);
}
bool backtrack(vector<int>& nums, int start, long long product, long long target) {
if (product == target) return true;
if (product > target || start >= nums.size()) return false;
for (int i = start; i < nums.size(); i++) {
if (backtrack(nums, i + 1, product * nums[i], target)) {
return true;
}
}
return false;
}
};class Solution {
public boolean checkEqualPartitions(int[] nums, long target) {
long total = 1;
for (int num : nums) {
total *= num;
if (total > target * target) return false;
}
if (total != target * target) return false;
return backtrack(nums, 0, 1, target);
}
private boolean backtrack(int[] nums, int start, long product, long target) {
if (product == target) return true;
if (product > target || start >= nums.length) return false;
for (int i = start; i < nums.length; i++) {
if (backtrack(nums, i + 1, product * nums[i], target)) {
return true;
}
}
return false;
}
}class Solution:
def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
total = 1
for num in nums:
total *= num
if total > target * target:
return False
if total != target * target:
return False
return self.backtrack(nums, 0, 1, target)
def backtrack(self, nums: List[int], start: int, product: int, target: int) -> bool:
if product == target:
return True
if product > target or start >= len(nums):
return False
for i in range(start, len(nums)):
if self.backtrack(nums, i + 1, product * nums[i], target):
return True
return False
Note:
- Backtracking approach may be too slow for larger inputs (n > 20) due to exponential time complexity.
- Due to there exponential time complexity, this code will cause Run Time Error.
Approach Comparison
| Approach | Time | Space | Readability | Optimal |
|---|---|---|---|---|
| Prime Factorization | O(n * 2^n) | O(n) | Moderate | ✅ |
| Backtracking | O(2^n) | O(n) | Simple | ❌ |
Recommendation: The prime factorization approach is more efficient for handling large products and constraints.
Edge Cases
1. Single Element Array
Input: nums = [5], target = 5 → Output: false (Need two non-empty subsets)2. All Elements Equal to Target
Input: nums = [2,2,2], target = 2 → Output: true ([2] and [2,2])3. Large Target Value
Input: nums = [1,2,3,4,5,6,7,8,9,10], target = 3628800 → Output: true
Testing Tip: Always test with arrays containing 1 and the target value itself.
Frequently Asked Questions
Why use prime factorization?
Prime factorization helps handle large products without overflow and allows comparison of exponents rather than actual products.
How does bitmasking help in this problem?
Bitmasking provides an efficient way to represent and iterate through all possible subsets of the array.
What's the time complexity of the prime factorization approach?
O(n * 2^n) in the worst case, but with pruning it's often much faster.
Can we use dynamic programming for this problem?
Yes, but it would require tracking products which could be very large and impractical for the given constraints.
How to handle duplicate elements?
The problem states all elements are distinct, so we don't need to handle duplicates.
What if the target is 1?
We need to find two subsets whose product is 1, which means one subset must contain only 1s.
Why check if total product equals target squared?
Because if we partition into two subsets with product target each, their combined product must be target × target.
How to optimize further?
We can sort the array in descending order to try larger elements first and prune more branches.
What's the maximum n this can handle?
With n=12, the bitmask approach is feasible (2^12 = 4096 subsets to check).
Can this be extended to k partitions?
Yes, but would require more complex tracking of multiple subset products.
Final Recommendation: The prime factorization with bitmasking approach provides the best balance between efficiency and correctness for this problem.