Partition array into two equal product subsets

Array Bit Manipulation Recursion Enumeration

35.1% acceptance

Feb 25, 2026

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 such that the product of each equals target.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn check_equal_partitions(nums: Vec<i32>, target: i64) -> bool {
    let n = nums.len();
    let total_product: i64 = nums.iter().map(|&x| x as i64).product();

    // Each element must be in subset A or B. product(A) = target, product(B) = target.
    // So total product = target^2.
    if total_product != target * target {
      return false;
    }

    // Find a non-empty proper subset with product = target
    // Enumerate all subsets
    for mask in 1u32..(1u32 << n) - 1 {
      let complement = ((1u32 << n) - 1) ^ mask;
      if complement == 0 { continue; }
      let prod_a: i64 = (0..n)
        .filter(|&i| mask & (1 << i) != 0)
        .map(|i| nums[i] as i64)
        .product();
      if prod_a == target {
        let prod_b: i64 = (0..n)
          .filter(|&i| complement & (1 << i) != 0)
          .map(|i| nums[i] as i64)
          .product();
        if prod_b == target {
          return true;
        }
      }
    }
    false
  }
}