LeetCode 3566 - Partition Array into Two Equal Product Subsets

Here’s a detailed technical solution guide for LeetCode 3566 following your formatting rules: The problem asks us to determine whether a given array of distinct positive integers can be split into two non-empty, disjoint subsets, such that the product of the elements in each…

leetcodemediumarraybit-manipulationrecursionenumeration

LeetCode Problem 3566

Difficulty: 🟡 Medium
Topics: Array, Bit Manipulation, Recursion, Enumeration

Solution

Here’s a detailed technical solution guide for LeetCode 3566 following your formatting rules:

Problem Understanding

The problem asks us to determine whether a given array of distinct positive integers can be split into two non-empty, disjoint subsets, such that the product of the elements in each subset equals a given target value. Each element of the array must belong to exactly one subset, meaning no element is shared between subsets.

The input consists of an array nums of length between 3 and 12, with values ranging from 1 to 100, and a target integer target up to $10^{15}$. The output is a boolean, true if such a partition exists, and false otherwise.

The constraints tell us that nums is small enough (max length 12) to consider combinatorial approaches like backtracking or bitmask enumeration. The large target value indicates that we need to be careful with integer multiplication and potential overflow, though Python handles big integers natively.

Important edge cases include arrays containing 1, which does not change the product, arrays where the product of all elements equals target, or arrays where target is a prime number that cannot be composed from any subset.

Approaches

The brute-force approach is to generate all possible subsets of nums, calculate their product, and check if there exists a subset whose product equals target. Then we check if the product of the remaining elements also equals target. This works because the problem size is small, but generating all subsets takes $O(2^n)$ time, which is feasible for n <= 12 but still not optimal.

The key insight for optimization is to use backtracking with pruning. We can recursively try to build subsets, multiplying numbers as we go. If at any point the product exceeds target, we prune that path because multiplying further will never equal target. Once we find a subset that multiplies to target, we check whether the remaining numbers also form a subset that multiplies to target.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(n) Generate all subsets and check products
Optimal O(2^(n/2)) O(2^(n/2)) Use meet-in-the-middle or backtracking with pruning

Algorithm Walkthrough

  1. Initial Check: If nums has fewer than 3 elements, return false immediately because we need two non-empty subsets.
  2. Generate All Subsets: Use recursion or bitmasking to generate all subsets of nums.
  3. Subset Product Calculation: For each subset, calculate the product. If the product exceeds target, skip further exploration.
  4. Check Complement Subset: If a subset has a product equal to target, calculate the product of the remaining elements. If it also equals target, return true.
  5. Backtracking: Recursively try including or excluding each number, backtracking if the current product exceeds target.
  6. Final Return: If no valid pair of subsets is found after checking all possibilities, return false.

Why it works: The algorithm explores all subset combinations systematically. Pruning ensures that we do not waste time on impossible paths. The check on the complement subset guarantees that each number is used exactly once.

Python Solution

from typing import List

class Solution:
    def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        
        def backtrack(index: int, current_product: int, used: List[bool]) -> bool:
            if current_product > target:
                return False
            if current_product == target:
                remaining_product = 1
                for i in range(n):
                    if not used[i]:
                        remaining_product *= nums[i]
                        if remaining_product > target:
                            return False
                return remaining_product == target
            
            if index == n:
                return False
            
            # Include nums[index]
            used[index] = True
            if backtrack(index + 1, current_product * nums[index], used):
                return True
            used[index] = False
            
            # Exclude nums[index]
            return backtrack(index + 1, current_product, used)
        
        return backtrack(0, 1, [False] * n)

The implementation uses a recursive backtracking function backtrack that tries to include or exclude each number. The used array tracks which numbers are part of the current subset. If the product exceeds target, we prune that branch. When we hit a subset whose product equals target, we check the remaining numbers for the second subset.

Go Solution

func checkEqualPartitions(nums []int, target int64) bool {
    n := len(nums)
    
    var backtrack func(index int, currentProduct int64, used []bool) bool
    backtrack = func(index int, currentProduct int64, used []bool) bool {
        if currentProduct > target {
            return false
        }
        if currentProduct == target {
            remainingProduct := int64(1)
            for i := 0; i < n; i++ {
                if !used[i] {
                    remainingProduct *= int64(nums[i])
                    if remainingProduct > target {
                        return false
                    }
                }
            }
            return remainingProduct == target
        }
        
        if index == n {
            return false
        }
        
        // Include nums[index]
        used[index] = true
        if backtrack(index+1, currentProduct*int64(nums[index]), used) {
            return true
        }
        used[index] = false
        
        // Exclude nums[index]
        return backtrack(index+1, currentProduct, used)
    }
    
    used := make([]bool, n)
    return backtrack(0, 1, used)
}

The Go version mirrors the Python logic, with attention to int64 to avoid integer overflow. The used slice tracks inclusion in the subset, and recursive calls explore both inclusion and exclusion.

Worked Examples

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

Step Index Current Product Used Array Remaining Product Action
1 0 3 [T,F,F,F,F] - Include 3
2 1 3 [T,F,F,F,F] - Exclude 1, include 6 next
3 2 18 [T,F,T,F,F] - Include 6
4 3 144 [T,F,T,F,F] - Exceeds target, backtrack
5 ... 24 [T,F,F,T,F] 24 Found valid partition [3,8] and [1,6,4]

Example 2: nums = [2,5,3,7], target = 15

All subset combinations are explored, but none produce both subsets with product 15. The function returns false.

Complexity Analysis

Measure Complexity Explanation
Time O(2^n * n) We explore all subsets, and checking the complement subset takes O(n)
Space O(n) Used array and recursion stack up to depth n

The recursive exploration scales exponentially, but pruning reduces the number of paths, especially when products exceed the target.

Test Cases

# Provided examples
assert Solution().checkEqualPartitions([3,1,6,8,4], 24) == True  # Example 1
assert Solution().checkEqualPartitions([2,5,3,7], 15) == False   # Example 2

# Edge and stress tests
assert Solution().checkEqualPartitions([1,1,1], 1) == True       # minimal numbers, all 1
assert Solution().checkEqualPartitions([2,4,8], 8) == True       # subset [8] and [2,4]
assert Solution().checkEqualPartitions([2,3,5,7], 6) == False    # no valid partition
assert Solution().checkEqualPartitions([1,2,3,6], 6) == True     # subset [6] and [1,2,3]
assert Solution().checkEqualPartitions([100,1,1,1], 100) == True # large number with small multipliers
Test Why
[3,1,6,8,4], 24 Valid partition exists
[2,5,3,7], 15 No partition possible
[1,1,1], 1 Minimal elements, product 1 edge case
[2,4,8], 8 Subsets with single and multiple elements
[2,3,5,7], 6 No possible combination
[1,2,3,6], 6 Check multiple small numbers forming product
[100,1,1,1], 100 Large target with ones

Edge Cases

Case 1: Target is 1

If target is 1, any subset containing only 1s can be valid. The algorithm correctly handles this because the product calculation

Problem Understanding

This problem asks whether an array of distinct positive integers can be split into exactly two **non-empty, disjoint subsets the product exceeds target, preventing unnecessary computation and avoiding overflow risks in stricter languages.