Partition Array into Two Equal Product Subsets - Solution & Explanation

Problem Overview: You are given an integer array and must determine whether it can be partitioned into two non‑empty subsets whose products are equal. Every element must belong to exactly one of the two groups. The core challenge is exploring different subset combinations while comparing their products.

Approach 1: Recursive Subset Enumeration (Backtracking) (Time: O(2^n), Space: O(n))

This approach generates all possible subsets using recursion. At each index you decide whether to include the current element in subset A or subset B. Track the running product of subset A while the product of subset B can be derived from the remaining elements. If at any point both subsets become non‑empty and their products match, you return true. The key idea is exhaustive exploration of every partition configuration. Recursion depth is at most n, so the stack space is O(n), while the number of states explored is O(2^n).

Approach 2: Binary Enumeration with Bit Masks (Time: O(2^n * n), Space: O(1))

Binary enumeration treats each subset as a bitmask where the i-th bit indicates whether nums[i] belongs to the first subset. Iterate from 1 to (1 << n) - 1 and compute the product of elements selected by the mask. The remaining elements implicitly form the second subset. If both subsets are non‑empty and their products match, the partition exists. This approach relies on bit manipulation to efficiently enumerate subsets and is often easier to implement than recursion. Each mask requires scanning up to n elements to compute the subset product, resulting in O(2^n * n) time.

One useful observation: if the total product of the array is P, the product of one subset must be sqrt(P) for the two subsets to match. During enumeration you can stop early if the running product exceeds this target or if P is not a perfect square. This pruning reduces unnecessary checks but does not change the worst‑case complexity.

The algorithm relies heavily on systematic subset generation, which is a common technique in problems involving arrays and exhaustive search. Bitmask enumeration is particularly effective when n is small (typically ≤ 20), since every subset can be explored within manageable time.

Recommended for interviews: Binary enumeration with bit masks. Interviewers expect you to recognize that the problem requires exploring all subset partitions and that bitmasks provide a compact, iterative way to generate them. Mentioning the recursive brute force first demonstrates problem‑solving intuition, while implementing the bitmask approach shows strong familiarity with subset enumeration patterns.