3566. 等积子集的划分方案 - Partition Array into Two Equal Product Subsets

🎯 问题描述（来源于LeetCode）

描述：
给定一个只包含不同正整数的数组 nums 和一个整数 target。你必须把 nums 所有元素分成两个非空且不相交的子集，每个元素恰好属于其中一个子集，使得两个子集的元素乘积都等于 target。若能找到则返回 true，否则返回 false。

说明：

每个元素只能属于其中一组，且两组都不能为空。
所有 nums 中的元素互不相同。
元素乘积可能非常大，需注意溢出（可使用 Python 大整数，或使用 target 的质因数分解优化，但本题数据范围小，暴力回溯即可）。

示例：

示例 1：

1
2
3

输入: nums = [3,1,6,8,4], target = 24
输出: true
解释: 子集 [3, 8] 和 [1, 6, 4] 的乘积均为 24。

示例 2：

1
2
3

输入: nums = [2,5,3,7], target = 15
输出: false
解释: 无法分割成两个乘积均为 15 的非空子集。

💻 解题思路

思路：回溯法（DFS） + 剪枝 + 非空子集验证

算法步骤

前置判断（总乘积）
计算 nums 所有元素的乘积 total_product，如果 total_product != target * target，直接返回 False（必要不充分条件，但可快速排除）。
回溯搜索
定义 dfs(i, cur_product, cnt)，表示当前考虑到下标 i，已选子集的乘积为 cur_product，已选元素个数为 cnt：
- 如果 i == n：所有元素处理完毕，此时若 cur_product == target 且 0 < cnt < n（即两个子集均非空），则返回 True，否则返回 False。
- 不选 nums[i]：递归 dfs(i+1, cur_product, cnt)，若返回 True 则直接返回。
- 选 nums[i]：将 cur_product 乘以 nums[i]，若新乘积不超过 target（剪枝），则递归 dfs(i+1, cur_product * nums[i], cnt+1)，若返回 True 则直接返回。
- 如果以上分支均未成功，返回 False。
从 dfs(0, 1, 0) 开始调用（初始乘积为 1，已选 0 个元素）。
返回最终结果。

代码实现

from typing import List

class Solution:
    def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
        total_product = 1
        for num in nums:
            total_product *= num
        if total_product != target * target:
            return False

        n = len(nums)
        # 因为元素为正整数，且 target 固定，乘积单调增，可以用排序 + 剪枝
        # 为了更好剪枝，可将 nums 降序排列（大的先选，更快超出 target 而回溯）
        nums.sort(reverse=True)

        def dfs(i: int, cur_product: int, cnt: int) -> bool:
            if i == n:
                # 两个子集均需非空：cnt > 0 且 cnt < n
                return cur_product == target and 0 < cnt < n
            # 不选当前元素
            if dfs(i + 1, cur_product, cnt):
                return True
            # 选当前元素，剪枝：乘积不能超过 target
            new_product = cur_product * nums[i]
            if new_product <= target and dfs(i + 1, new_product, cnt + 1):
                return True
            return False

        return dfs(0, 1, 0)

📊 性能分析

时间复杂度：最坏 $O(2^n)$ ，但通过排序 + 乘积剪枝，实际运行远快于朴素回溯。
空间复杂度： $O(n)$ ，递归栈深度。

思考

通过 cnt 参数确保子集非空。
为了进一步提高剪枝效率，将 nums 降序排列，使较大元素优先尝试，能更快超过 target 从而回溯，减少搜索空间。
若数组长度较大（例如 > 20），回溯仍可能超时，此时可考虑 Meet-in-the-Middle 或 DP（但由于乘积巨大，DP 不现实）。题目数据范围通常较小，此解法足够。