3566. Partition Array into Two Equal Product Subsets

MediumBit ManipulationRecursionArrayEnumeration

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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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 from 0 to 2^n - 1, the binary representation of i indicates which subset each element goes into. If the j-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, return true.
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 Evaluator

Example 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 (binary 010) 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]

dp[i] = dp[i - 1] + 1

dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

dp[i] = dp[i - 1]

I don't know