M3566.等积子集的划分方案

bitmask, https://leetcode.cn/problems/partition-array-into-two-equal-product-subsets/

给你一个整数数组 nums，其中包含的正整数 互不相同 ，另给你一个整数 target。

请判断是否可以将 nums 分成两个非空、互不相交 的子集，并且每个元素必须恰好属于一个子集，使得这两个子集中元素的乘积都等于 target。

如果存在这样的划分，返回 true；否则，返回 false。

子集是数组中元素的一个选择集合。

示例 1：

输入： nums = [3,1,6,8,4], target = 24

输出： true

解释：子集 [3, 8] 和 [1, 6, 4] 的乘积均为 24。因此，输出为 true 。

示例 2：

输入： nums = [2,5,3,7], target = 15

输出： false

解释：无法将 nums 划分为两个非空的互不相交子集，使得它们的乘积均为 15。因此，输出为 false。

提示：

3 <= nums.length <= 12
1 <= target <= 10^15
1 <= nums[i] <= 100
nums 中的所有元素互不相同。

我们可以使用 回溯 + 枚举子集乘积 来解决这个问题。

由于 nums.length <= 12，我们可以枚举 nums 的所有非空子集并计算它们的乘积，只要这个乘积等于 target，就将它作为候选子集。然后我们需要从中找出两个 互不相交 的子集，使得这两个子集的乘积都为 target，并且它们加起来刚好覆盖 nums 的一个真子集（两者并集是 nums 的子集，但不能是空集或相等）。

✅ 关键点：

用位掩码枚举 nums 的所有非空子集（从 1 到 2^n - 2，排除空集和全集）。
记录所有乘积为 target 的子集及其位掩码。
检查这些子集中是否有两个互不相交的（即 mask1 & mask2 == 0），并且它们的并集刚好是 nums 的一部分（这里是全集也可以，因为题目只要求两个非空、互不相交、每个元素只属于一个子集即可）。

✅ 实现代码如下：

python

from typing import List
from math import prod

class Solution:
    def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        index_map = {i: nums[i] for i in range(n)}
        valid_subsets = []

        # 枚举所有子集（掩码从 1 到 2^n - 2，排除空集和全集）
        full_mask = (1 << n) - 1
        for mask in range(1, full_mask):
            subset = [nums[i] for i in range(n) if (mask >> i) & 1]
            p = 1
            for x in subset:
                p *= x
                if p > target:
                    break
            if p == target:
                valid_subsets.append(mask)

        # 检查是否存在两个互不相交的子集，乘积都等于 target
        for i in range(len(valid_subsets)):
            for j in range(i + 1, len(valid_subsets)):
                if valid_subsets[i] & valid_subsets[j] == 0:
                    if (valid_subsets[i] | valid_subsets[j]) == full_mask:
                        return True

        return False

✅ 复杂度分析：

时间复杂度：O(2^n * n)，其中 n 是 nums.length，因为我们要枚举所有子集，并计算乘积。
空间复杂度：O(2^n)，用于存储所有合法子集的掩码。

由于 n <= 12，最多枚举 4096 个子集，是可以接受的。

M3566.等积子集的划分方案 ​

M3566.等积子集的划分方案