# Partition Array into Two Equal Product Subsets
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/partition-array-into-two-equal-product-subsets)
Canonical: https://scaleengineer.com/dsa/problems/partition-array-into-two-equal-product-subsets
**Patterns:** [Recursion](https://scaleengineer.com/dsa/patterns/recursion), [Bit Manipulation](https://scaleengineer.com/dsa/patterns/bit-manipulation), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
---
## 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.

A **subset** of an array is a selection of elements of the array. 

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

# Approaches
## Brute-force Backtracking
This approach uses a classic backtracking algorithm to explore every possible subset of the `nums` array. For each element, it makes a choice to either include it in the current subset or not, recursively building up potential solutions. If a subset is found whose elements multiply to the `target` value, we have found a valid partition.
**Time:** O(2^N), where N is the number of elements in `nums`. In the worst-case scenario, the algorithm explores all 2^N possible subsets. · **Space:** O(N), where N is the number of elements in `nums`. This space is used by the recursion call stack.
**Pros:** Conceptually simple and straightforward to implement.; Uses minimal space, only for the recursion stack.
**Cons:** The time complexity is exponential, O(2^N), which is slow for larger N.; It may perform redundant computations for the same subproblems (i.e., reaching the same product at the same index via different paths).
### Explanation
The core idea is to systematically generate all 2^N subsets of the input array `nums`. Before starting the search, we make a vital optimization: we calculate the product of all elements in `nums`. For a valid partition to exist, this total product must be exactly `target * target`. If this condition doesn't hold, we can immediately return `false`. This check requires using `BigInteger` to handle potentially large numbers without overflow.

If the total product check passes, we then proceed with a recursive search. The function, say `canFindSubset(index, currentProduct)`, tries to build a subset with the desired product. At each step `index`, it considers `nums[index]` and branches into two possibilities: one where `nums[index]` is included in the subset (multiplying it with `currentProduct`) and one where it's excluded. The recursion terminates when a product equals `target` (success), exceeds `target` (failure), or all elements have been considered (failure).

Because the problem guarantees `nums` contains distinct positive integers and has a length of at least 3, any subset found with a product of `target` will necessarily be a non-empty, proper subset, thus guaranteeing that the other subset in the partition is also non-empty.
### Algorithm
- First, perform a crucial preliminary check: the product of all elements in `nums` must equal `target * target`. If not, a valid partition is impossible. Use `BigInteger` for this calculation to avoid overflow.
- If the check passes, the problem reduces to finding a single non-empty, proper subset with a product equal to `target`.
- Implement a recursive function, `canFindSubset(index, currentProduct)`, to explore all subsets.
- **Base Cases:**
  - If `currentProduct == target`, a subset is found, return `true`.
  - If `currentProduct > target` or `index` is out of bounds, this path is invalid, return `false`.
- **Recursive Step:** For each element `nums[index]`, make two recursive calls:
  1. **Exclude:** `canFindSubset(index + 1, currentProduct)`.
  2. **Include:** `canFindSubset(index + 1, currentProduct * nums[index])`. This call is only made if the new product won't immediately exceed `target` and `target` is divisible by it.
- If either recursive call returns `true`, propagate `true` up the call stack.
- The initial call is `canFindSubset(0, 1)`. If it returns `true`, a valid partition exists.

## Backtracking with Memoization
This approach enhances the brute-force backtracking solution by adding memoization, a top-down dynamic programming technique. It stores the results of previously solved subproblems in a cache (like a hash map) to avoid re-computation. The state of a subproblem is defined by the current index being considered and the product of the elements chosen so far.
**Time:** O(N * P), where N is the array length and P is the number of unique subset products. The worst-case complexity is O(2^N), but it's often much faster in practice. · **Space:** O(N * P), where N is the array length and P is the number of unique subset products. In the worst case, this can be O(2^N) if most subset products are unique.
**Pros:** Faster than plain backtracking in practice due to avoiding redundant calculations.; Guaranteed to solve each subproblem only once.
**Cons:** The space complexity can be large, potentially O(2^N) in the worst case, as it needs to store results for many states.; The worst-case time complexity is still exponential.
### Explanation
While the simple backtracking approach can be inefficient due to re-calculating results for the same subproblems, we can optimize it by storing these results. A subproblem can be uniquely identified by the pair `(index, currentProduct)`. We use an array of hash maps, `memo`, where `memo[index]` maps a `currentProduct` to the boolean result of whether a subset with product `target` can be formed from that state.

When the recursive function `canFindSubset(index, currentProduct, memo)` is called, it first checks if the result for this state is already in the `memo` table. If it is, the stored result is returned immediately. Otherwise, the result is computed recursively, as in the brute-force method. Once the result is determined (either `true` or `false`), it is stored in `memo[index]` with `currentProduct` as the key before being returned. This trade-off of space for time significantly speeds up the computation if there are many overlapping subproblems (i.e., different combinations of numbers leading to the same intermediate product).
### Algorithm
- The overall logic is identical to the brute-force approach, including the initial `totalProduct == target * target` check.
- The key difference is the use of a memoization table, e.g., `Map<Long, Boolean>[] memo`, to store the results of subproblems.
- The state for memoization is `(index, currentProduct)`.
- Before computing `canFindSubset(index, currentProduct)`, check if the result is already in `memo[index]` for the key `currentProduct`. If yes, return the stored value.
- After computing the result for `(index, currentProduct)`, store it in the memoization table before returning.
- This ensures that each unique subproblem is solved only once.

## Meet-in-the-Middle
The Meet-in-the-Middle technique is a highly efficient approach that leverages the small size of the input array. It splits the problem in two, solving each half independently and then combining the results. By dividing the array, it dramatically reduces the exponential complexity, making it the fastest solution for the given constraints.
**Time:** O(2^(N/2)), where N is the length of `nums`. This comes from generating 2^(N/2) products for each half and performing lookups. · **Space:** O(2^(N/2)) to store the subset products of the first half of the array in a hash set.
**Pros:** Significantly more efficient with a time complexity of O(2^(N/2)).; The most optimal solution for the given constraints.
**Cons:** Slightly more complex to implement than a simple backtracking solution.; Requires additional space to store the subset products of the first half.
### Explanation
This approach begins with the same crucial check of the total product against `target * target`. The main strategy is to divide and conquer. The `nums` array is split into two smaller halves. 

First, we generate all possible subset products for the first half of the array and store them in a hash set for O(1) average time lookups. The number of subsets for this half is 2^(N/2), which is very manageable for N <= 12.

Next, we process the second half. Instead of storing all its subset products, we generate them one by one. For each subset product `p2` from the second half, we calculate the product `p1` that we would need from the first half to achieve the target (i.e., `p1 = target / p2`). We then check if this required `p1` exists in our hash set of products from the first half. If we find such a `p1`, we have successfully found a combination of subsets from both halves that multiply to `target`, and we can return `true`.

This method reduces the time complexity from O(2^N) to O(2^(N/2)), which is a significant improvement. For N=12, this changes the number of operations from ~4096 to ~64, making the solution extremely fast.
### Algorithm
- Perform the initial check: if `product(nums) != target * target`, return `false`.
- Split the `nums` array into two halves: `leftHalf` (from index 0 to `N/2 - 1`) and `rightHalf` (from index `N/2` to `N-1`).
- Define a helper function `generateProducts` to find all possible subset products for a given subarray. This can be done recursively.
- Call `generateProducts` on `leftHalf` to get a set of all its subset products, `products1`.
- Call `generateProducts` on `rightHalf` to get a set of its subset products, `products2`.
- Iterate through each product `p1` in `products1`.
- For each `p1`, check if `target` is divisible by `p1`.
- If it is, calculate the required product `p2 = target / p1`.
- Check if this `p2` exists in the `products2` set.
- If a match is found, it means we can form a subset with product `target` by combining a subset from the left half and a subset from the right half. Return `true`.
- If the loop completes without finding a match, return `false`.

# Solutions
### Java

```java
class 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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```