#3566

Medium

LeetCode Problem Workspace

Partition Array into Two Equal Product Subsets

Determine if you can partition an array into two subsets with equal product using recursion and bit manipulation.

array bit manipulation recursion enumeration

Problem Statement

You are given an array of distinct positive integers and a target value. Your task is to determine if it is possible to partition the array into two non-empty disjoint subsets, such that the product of the elements in each subset equals the target value.

Return true if such a partition exists, or false if it does not. Consider all possible subsets of the array to check if the condition holds for any partition.

Examples

Example 1

Input: nums = [3,1,6,8,4], target = 24

Output: true

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

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 <= 12
1 <= target <= 1015
1 <= nums[i] <= 100
All elements of nums are distinct.

Solution Approach

Subset Enumeration

Enumerate all subsets of the array using bit manipulation, checking if any partition of the subsets results in products that match the target.

Recursive Checking

Use recursion to split the array into subsets, checking if each partition of elements results in the same product. This reduces the problem into smaller, manageable checks.

Optimization with Early Termination

To optimize the approach, early terminate the search when the product of any subset exceeds the target value, reducing unnecessary checks.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the number of subsets and the recursion depth, both of which grow exponentially with the array size. Thus, this problem has an exponential time complexity. Space complexity depends on the depth of recursion and the bit manipulation used to store subsets, but it is also exponential in nature.

What Interviewers Usually Probe

Candidate understands how bit manipulation can help enumerate subsets efficiently.
Candidate can optimize recursion using early termination to avoid unnecessary calculations.
Candidate recognizes that the problem is inherently exponential in complexity.

Common Pitfalls or Variants

Common pitfalls

Incorrectly handling subsets, leading to redundant calculations or missing valid partitions.
Not using early termination, causing inefficient solutions that exceed time limits.
Forgetting to check if all elements are used in one subset, which violates the partition condition.

Follow-up variants

Consider larger arrays where performance optimization through pruning and dynamic programming may be necessary.
Modify the problem by allowing subsets to contain zero or more elements instead of requiring non-empty subsets.
Change the target value dynamically during runtime to test how the algorithm adapts.

FAQ

What is the core pattern in the 'Partition Array into Two Equal Product Subsets' problem?

The core pattern involves array manipulation combined with bit manipulation to enumerate all subsets, checking their products against a target.

How does bit manipulation help solve the Partition Array into Two Equal Product Subsets problem?

Bit manipulation allows you to efficiently generate subsets of the array, making it possible to check every possible partition for matching products.

What is the time complexity of solving the Partition Array into Two Equal Product Subsets problem?

The time complexity is exponential, primarily due to the need to generate and check all possible subsets of the array.

Can recursion be used to solve this problem? How?

Yes, recursion can be used to split the array into smaller subsets, and each partition's product can be recursively checked against the target value.

What is a common mistake in solving the Partition Array into Two Equal Product Subsets problem?

A common mistake is failing to apply early termination in recursion, causing the solution to check unnecessary subsets and exceed time limits.

terminal

Solution

Solution 1: Binary Enumeration

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

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 False

Continue Practicing

#3514 number of unique xor triplets ii #3483 unique 3 digit even numbers #3435 frequencies of shortest supersequences