跳转至

3566. 等积子集的划分方案

题目描述

给你一个整数数组 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 <= 1015
  • 1 <= nums[i] <= 100
  • nums 中的所有元素互不相同。

解法

方法一：二进制枚举

我们可以使用二进制枚举的方式来检查所有可能的子集划分。对于每个子集划分，我们可以计算两个子集的乘积，并检查它们是否都等于目标值。

具体地，我们可以使用一个整数 \(i\) 来表示子集划分的状态，其中 \(i\) 的二进制位表示每个元素是否属于第一个子集。对于每个可能的 \(i\)，我们可以计算两个子集的乘积，并检查它们是否都等于目标值。

时间复杂度 \(O(2^n \times n)\)，其中 \(n\) 是数组的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
        n = len(nums)
        for i in range(1 << n):
            x = y = 1
            for j in range(n):
                if i >> j & 1:
                    x *= nums[j]
                else:
                    y *= nums[j]
            if x == target and y == target:
                return True
        return False

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean checkEqualPartitions(int[] nums, long target) {
        int n = nums.length;
        for (int i = 0; i < 1 << n; ++i) {
            long x = 1, y = 1;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    x *= nums[j];
                } else {
                    y *= nums[j];
                }
            }
            if (x == target && y == target) {
                return true;
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    bool checkEqualPartitions(vector<int>& nums, long long target) {
        int n = nums.size();
        for (int i = 0; i < 1 << n; ++i) {
            long long x = 1, y = 1;
            for (int j = 0; j < n; ++j) {
                if ((i >> j & 1) == 1) {
                    x *= nums[j];
                } else {
                    y *= nums[j];
                }
                if (x > target || y > target) {
                    break;
                }
            }
            if (x == target && y == target) {
                return true;
            }
        }
        return false;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
func checkEqualPartitions(nums []int, target int64) bool {
    n := len(nums)
    for i := 0; i < 1<<n; i++ {
        x, y := int64(1), int64(1)
        for j, v := range nums {
            if i>>j&1 == 1 {
                x *= int64(v)
            } else {
                y *= int64(v)
            }
            if x > target || y > target {
                break
            }
        }
        if x == target && y == target {
            return true
        }
    }
    return false
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function checkEqualPartitions(nums: number[], target: number): boolean {
    const n = nums.length;
    for (let i = 0; i < 1 << n; ++i) {
        let [x, y] = [1, 1];
        for (let j = 0; j < n; ++j) {
            if (((i >> j) & 1) === 1) {
                x *= nums[j];
            } else {
                y *= nums[j];
            }
            if (x > target || y > target) {
                break;
            }
        }
        if (x === target && y === target) {
            return true;
        }
    }
    return false;
}

评论