Medium

题目描述

给你一个包含不同正整数的整数数组 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 的所有元素都不相同

提示：

  • 尝试遍历所有子集
  • 使用位掩码

解题思路

这是一个经典的子集分割问题，需要将数组分成两个子集，使得每个子集的乘积都等于目标值。

解题思路

基本思路：

  1. 由于数组长度最多为12，我们可以使用位掩码枚举所有可能的子集
  2. 对于每个子集，计算其乘积是否等于target
  3. 如果找到一个乘积为target的子集，检查剩余元素的乘积是否也为target

优化策略：

  • 首先计算所有数字的总乘积，如果不等于target²，直接返回false
  • 使用位运算快速枚举子集，避免递归开销
  • 提前剪枝：如果当前乘积已经超过target，跳过后续计算

算法步骤：

  1. 计算总乘积，验证是否为target的平方
  2. 使用位掩码从1到2^n-2枚举所有非空真子集
  3. 对每个子集计算乘积，如果等于target则检查补集
  4. 找到满足条件的分割则返回true

时间复杂度为O(2^n × n)，空间复杂度为O(1)，适合题目给定的数据规模。

代码实现

class Solution {
public:
    bool checkEqualPartitions(vector<int>& nums, long long target) {
        int n = nums.size();
        
        // 计算总乘积
        long long totalProduct = 1;
        for (int num : nums) {
            totalProduct *= num;
        }
        
        // 如果总乘积不等于target的平方，无法分割
        if (totalProduct != target * target) {
            return false;
        }
        
        // 枚举所有可能的子集（除了空集和全集）
        for (int mask = 1; mask < (1 << n) - 1; mask++) {
            long long product = 1;
            
            // 计算当前子集的乘积
            for (int i = 0; i < n; i++) {
                if (mask & (1 << i)) {
                    product *= nums[i];
                    // 剪枝：如果乘积已经超过target，跳出
                    if (product > target) break;
                }
            }
            
            // 如果当前子集乘积等于target，检查补集
            if (product == target) {
                return true;
            }
        }
        
        return false;
    }
};

class Solution:
    def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        
        # 计算总乘积
        total_product = 1
        for num in nums:
            total_product *= num
        
        # 如果总乘积不等于target的平方，无法分割
        if total_product != target * target:
            return False
        
        # 枚举所有可能的子集（除了空集和全集）
        for mask in range(1, (1 << n) - 1):
            product = 1
            
            # 计算当前子集的乘积
            for i in range(n):
                if mask & (1 << i):
                    product *= nums[i]
                    # 剪枝：如果乘积已经超过target，跳出
                    if product > target:
                        break
            
            # 如果当前子集乘积等于target，返回True
            if product == target:
                return True
        
        return False

public class Solution {
    public bool CheckEqualPartitions(int[] nums, long target) {
        int n = nums.Length;
        
        // 计算总乘积
        long totalProduct = 1;
        foreach (int num in nums) {
            totalProduct *= num;
        }
        
        // 如果总乘积不等于target的平方，无法分割
        if (totalProduct != target * target) {
            return false;
        }
        
        // 枚举所有可能的子集（除了空集和全集）
        for (int mask = 1; mask < (1 << n) - 1; mask++) {
            long product = 1;
            
            // 计算当前子集的乘积
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    product *= nums[i];
                    // 剪枝：如果乘积已经超过target，跳出
                    if (product > target) break;
                }
            }
            
            // 如果当前子集乘积等于target，返回true
            if (product == target) {
                return true;
            }
        }
        
        return false;
    }
}

var checkEqualPartitions = function(nums, target) {
    const n = nums.length;
    const totalProduct = nums.reduce((a, b) => a * b, 1);
    
    if (totalProduct !== target * target) return false;
    
    function backtrack(index, product1, count1) {
        if (index === n) {
            return count1 > 0 && count1 < n && product1 === target;
        }
        
        return backtrack(index + 1, product1 * nums[index], count1 + 1) ||
               backtrack(index + 1, product1, count1);
    }
    
    return backtrack(0, 1, 0);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(2^n × n)需要枚举2^n个子集，每个子集最多有n个元素
空间复杂度O(1)只使用常数级别的额外空间

其中n为数组长度，由于题目限制n ≤ 12，所以时间复杂度在可接受范围内。