3566. Partition Array into Two Equal Product Subsets
Problem Description
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.
A subset of an array is a selection of elements of the array.
Intuition
We need to divide the array into two non-empty subsets where the product of elements in each subset is exactly target
. Since the array elements are all distinct positive integers, the only way to do this is to check all possible ways to split the array into two groups.
For each possible split, we calculate the product of each subset. If both products equal target
, then a valid partition exists. Because subsets can be represented by binary bits (each bit indicating whether an element is in the first subset or the second), we can conveniently use binary representation to try every possible way of splitting the array.
This systematic check ensures no partition is missed, and since nums
is relatively small, this brute force way is manageable in practice.
Solution Approach
The solution uses binary enumeration to explore all possible ways of partitioning the array into two disjoint non-empty subsets.
For an array nums
of length n
, each element has two possibilities: it can either be in the first subset or the second subset. This gives us 2^n
possible ways to divide the elements.
The approach is as follows:
- For each value of
i
from0
to2^n - 1
, the binary representation ofi
indicates which subset each element goes into. If thej
-th bit is set,nums[j]
is in the first subset; otherwise, it's in the second subset. - For every possible partition, calculate the product of elements in both subsets.
- If both products are equal to
target
and both subsets are non-empty, returntrue
. - If no such partition is found after checking all possibilities, return
false
.
The code uses two variables x
and y
to keep track of the products for the two subsets while iterating. By multiplying the selected elements according to the current bitmask, we efficiently check every partition possibility.
This approach leverages bit manipulation to represent subsets efficiently and brute-forces all subset divisions due to the small constraint on n
.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use the array nums = [2, 4, 8]
and target = 8
as an example.
Step-by-step:
- There are 3 elements, so there are
2^3 = 8
possible ways to split them using binary masks from 1 to 6 (skipping 0 and 7, which are all-in-one-subset cases). - For each possible mask, divide the elements into two groups based on each bit. For example, mask
i = 2
(binary010
) means only the second element (4) is in subset A, and the rest (2, 8) are in subset B. - Calculate products for the two groups and check if both equal
target
and both subsets are non-empty.
Let's walk through the masks:
Mask (binary) | Subset 1 | Subset 2 | Product 1 | Product 2 | Both==target? |
---|---|---|---|---|---|
001 | [2] | [4, 8] | 2 | 32 | No |
010 | [4] | [2, 8] | 4 | 16 | No |
011 | [2, 4] | [8] | 8 | 8 | Yes |
100 | [8] | [2, 4] | 8 | 8 | Yes |
101 | [2, 8] | [4] | 16 | 4 | No |
110 | [4, 8] | [2] | 32 | 2 | No |
Masks 011
and 100
split the array into two non-empty subsets with products [2, 4] = 8
and [8] = 8
, and vice versa. So, the function should return true
.
This illustrates how the bitmask approach checks all subsets to find a partition where both groups multiply to the target.
Solution Implementation
1from typing import List
2
3class Solution:
4 def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
5 n = len(nums)
6 # Iterate through all possible ways to divide nums into two groups using bitmasking
7 for mask in range(1 << n):
8 prod_group1 = 1 # Product of selected elements (where bit is set)
9 prod_group2 = 1 # Product of remaining elements (where bit is not set)
10 for j in range(n):
11 if (mask >> j) & 1:
12 prod_group1 *= nums[j]
13 else:
14 prod_group2 *= nums[j]
15 # Check if both groups produce the target product
16 if prod_group1 == target and prod_group2 == target:
17 return True
18 return False
19
1class Solution {
2 /**
3 * Checks if it is possible to partition the input array 'nums' into two groups
4 * such that the product of elements in each group equals the given 'target'.
5 *
6 * @param nums An array of integers.
7 * @param target The product target for both partitions.
8 * @return True if such a partition exists, otherwise false.
9 */
10 public boolean checkEqualPartitions(int[] nums, long target) {
11 int n = nums.length;
12 // Iterate over all possible subsets (2^n possibilities)
13 for (int mask = 0; mask < (1 << n); ++mask) {
14 long productA = 1;
15 long productB = 1;
16 // For each bit in mask, decide whether to include nums[j] in productA or productB
17 for (int j = 0; j < n; ++j) {
18 if (((mask >> j) & 1) == 1) {
19 // If j-th bit is set, include nums[j] in productA
20 productA *= nums[j];
21 } else {
22 // Else, include nums[j] in productB
23 productB *= nums[j];
24 }
25 }
26 // Check if both groups' products are equal to target
27 if (productA == target && productB == target) {
28 return true;
29 }
30 }
31 // No valid partition found
32 return false;
33 }
34}
35
1class Solution {
2public:
3 // Checks if the array can be partitioned into two groups whose products both equal target
4 bool checkEqualPartitions(vector<int>& nums, long long target) {
5 int n = nums.size();
6 // There are 2^n possible ways to assign each element to one of two groups
7 for (int mask = 0; mask < (1 << n); ++mask) {
8 long long productA = 1, productB = 1;
9 // Iterate through each element and decide which group it belongs to based on mask
10 for (int bit = 0; bit < n; ++bit) {
11 if ((mask >> bit) & 1) {
12 // Assign nums[bit] to group A
13 productA *= nums[bit];
14 } else {
15 // Assign nums[bit] to group B
16 productB *= nums[bit];
17 }
18 // Early stopping to avoid unnecessary computation if product exceeds target
19 if (productA > target || productB > target) {
20 break;
21 }
22 }
23 // Check if both groups' products equal to target
24 if (productA == target && productB == target) {
25 return true;
26 }
27 }
28 // No valid partition found
29 return false;
30 }
31};
32
1/**
2 * Determines if an array of numbers can be partitioned into two groups
3 * whose products are both equal to the target value.
4 *
5 * @param nums - An array of positive integers.
6 * @param target - The product value each group should reach.
7 * @returns True if such a partition exists, otherwise false.
8 */
9function checkEqualPartitions(nums: number[], target: number): boolean {
10 const n = nums.length;
11 // Loop through all possible ways to partition the array using bitmasks
12 for (let mask = 0; mask < (1 << n); ++mask) {
13 let productGroupA = 1;
14 let productGroupB = 1;
15 // Assign each number to a group based on the current bitmask
16 for (let idx = 0; idx < n; ++idx) {
17 if (((mask >> idx) & 1) === 1) {
18 productGroupA *= nums[idx];
19 } else {
20 productGroupB *= nums[idx];
21 }
22 // Early exit if any group's product exceeds the target
23 if (productGroupA > target || productGroupB > target) {
24 break;
25 }
26 }
27 // Check if both groups' products match the target
28 if (productGroupA === target && productGroupB === target) {
29 return true;
30 }
31 }
32 // No valid partition found
33 return false;
34}
35
Time and Space Complexity
The time complexity of the code is O(2^n * n)
, where n
is the length of the input array nums
. This is because the code iterates over all possible subsets (2^n
combinations), and for each combination, it iterates over n
elements to compute the two products.
The space complexity is O(1)
since the algorithm uses only a constant amount of extra space regardless of the input size.
Which of the following shows the order of node visit in a Breadth-first Search?
Recommended Readings
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Donβt Miss This!