2025-11-15：等积子集的划分方案。用go语言，给定一个只包含不同正整数的数组 nums 和一个整数 target。要求把

福大大架构师每日一题

发布于 2025-12-19 09:06:04

1390

2025-11-15：等积子集的划分方案。用go语言，给定一个只包含不同正整数的数组 nums 和一个整数 target。要求把 nums 的所有元素分成两组（每个元素只能属于其中一组，且两组都不能为空），使得每一组中所有数相乘的结果都等于 target。若存在这样的分组返回 true，否则返回 false。

3 <= nums.length <= 12。

1 <= target <= 1000000000000000。

1 <= nums[i] <= 100。

nums 中的所有元素互不相同。

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

输出： true。

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

题目来自力扣3566。

分步骤详细过程

1. 整体乘积验证
- • 首先，计算整个数组 nums 中所有元素的乘积。如果整个数组的乘积不等于 target 的平方（即 target * target），则直接返回 false。这是因为问题要求将数组划分为两个子集后，每个子集的乘积都等于 target，因此整个数组的乘积必须恰好为 target²。
- • 例如，在示例 nums = [3,1,6,8,4] 和 target = 24 中，整个数组的乘积为 3*1*6*8*4 = 576，而 24² = 576，因此通过验证。
2. 分治分割数组
- • 将数组 nums 近似分成两半：前半部分为 nums[:m]，后半部分为 nums[m:]，其中 m 是 len(nums) / 2（例如，当 n=5 时，前半部分包含前2个或3个元素，具体取决于实现）。这种分治策略的目的是将指数级复杂度的枚举问题分解为两个规模减半的子问题。
- • 分治后，前半部分和后半部分分别独立处理，减少需要枚举的状态数。
3. 生成前半部分的乘积比例集合（使用DFS）
- • 对前半部分数组执行DFS，递归地枚举每个元素被划分到第一个子集（记为乘积 a）或第二个子集（记为乘积 b）的所有可能方式。DFS的起点为 a=1 和 b=1（乘法的单位元）。
- • 当处理完前半部分所有元素后，计算 a 和 b 的最简分数比例：即计算 a 和 b 的最大公约数（GCD），然后将比例简化为 (a/gcd, b/gcd)。这个比例表示两个子集乘积的相对大小，而非具体值，从而避免数值溢出并简化匹配。
- • 所有最简比例被存储在一个集合 set1 中（例如，使用Map结构，键为比例对）。如果DFS过程中 a 或 b 超过 target，则剪枝提前返回，因为后续乘法只会使乘积更大。
4. 生成后半部分的乘积比例集合（同样使用DFS）
- • 对后半部分数组执行相同的DFS过程：枚举每个元素划分到第一个子集（乘积记为 c）或第二个子集（乘积记为 d）的所有情况。
- • 处理完后半部分后，同样计算 c 和 d 的最简比例 (c/gcd, d/gcd)，并存储在另一个集合 set2 中。
5. 合并检查比例匹配
- • 检查 set1 和 set2 中是否存在相同的比例对。如果存在这样的比例，则表明可以将前半部分和后半部分的划分组合成一个有效解：
  - • 具体来说，如果前半部分的比例为 (p, q)，后半部分的比例为 (q, p)，则组合后整个数组的第一个子集乘积为 p * q = target，第二个子集乘积为 q * p = target（因为整个数组乘积为 target²）。
- • 例如，示例中前半部分可能生成比例 (3, 1)（对应子集乘积为3和1），后半部分生成比例 (8, 2)，但需注意实际匹配时比例需互补。代码中通过集合查找直接验证是否存在公共比例。
- • 如果找到匹配，返回 true；否则返回 false。

总时间复杂度和总额外空间复杂度

• 时间复杂度：
- • 整个过程的核心是DFS枚举。数组长度 n 最大为12，分治后每半部分长度约为 n/2（即最多6）。DFS枚举每半部分的所有划分方式，每个元素有2种选择（分配给第一个或第二个子集），因此每半部分的DFS状态数为 O(2^{n/2})。
- • 计算GCD的时间可视为常数（因为数字乘积受 target ≤ 10^15 和 nums[i] ≤ 100 限制，数值范围有限）。
- • 总时间复杂度为 O(2^{n/2})，分治策略将指数基数减半，优于直接枚举的 O(2^n)。
• 总额外空间复杂度：
- • 主要空间开销用于存储两个比例集合 set1 和 set2。每个集合最多包含 O(2^{n/2}) 个比例对（每个比例对是两个整数）。
- • DFS递归栈的深度为 O(n)，空间可忽略。
- • 因此，总额外空间复杂度为 O(2^{n/2})。

该方法通过分治和比例匹配巧妙降低了计算复杂度，适用于题目中的小规模约束（n ≤ 12）。

Go完整代码如下：

package main

import (
    "fmt"
    "math/big"
)

func calc(nums []int, target int)map[[2]int]struct{} {
    set := map[[2]int]struct{}{}
    var dfs func(int, int, int)
    dfs = func(i, a, b int) {
        if a > target || b > target {
            return
        }
        if i == len(nums) {
            g := gcd(a, b)
            set[[2]int{a / g, b / g}] = struct{}{} // 最简分数
            return
        }
        dfs(i+1, a*nums[i], b)
        dfs(i+1, a, b*nums[i])
    }
    dfs(0, 1, 1)
    return set
}

func checkEqualPartitions(nums []int, target int64)bool {
    prodAll := big.NewInt(1)
    for _, x := range nums {
        prodAll.Mul(prodAll, big.NewInt(int64(x)))
    }
    square := big.NewInt(target)
    square.Mul(square, square)
    if prodAll.Cmp(square) != 0 {
        returnfalse
    }

    m := len(nums) / 2
    set1 := calc(nums[:m], int(target))
    set2 := calc(nums[m:], int(target))

    for p := range set1 {
        if _, ok := set2[p]; ok {
            returntrue
        }
    }
    returnfalse
}

func gcd(a, b int)int {
    for a != 0 {
        a, b = b%a, a
    }
    return b
}

func main() {
    nums := []int{3, 1, 6, 8, 4}
    target := 24
    result := checkEqualPartitions(nums, int64(target))
    fmt.Println(result)
}

Python完整代码如下：

# -*-coding:utf-8-*-

import math
from typing import List, Set, Tuple

def calc(nums: List[int], target: int) -> Set[Tuple[int, int]]:
    s = set()
    
    def dfs(i: int, a: int, b: int):
        if a > target or b > target:
            return
        if i == len(nums):
            g = math.gcd(a, b)
            s.add((a // g, b // g))  # 最简分数
            return
        dfs(i + 1, a * nums[i], b)
        dfs(i + 1, a, b * nums[i])
    
    dfs(0, 1, 1)
    return s

def check_equal_partitions(nums: List[int], target: int) -> bool:
    total_product = 1
    for x in nums:
        total_product *= x
    
    if total_product != target * target:
        return False
    
    m = len(nums) // 2
    set1 = calc(nums[:m], target)
    set2 = calc(nums[m:], target)
    
    for p in set1:
        if p in set2:
            return True
    return False

if __name__ == "__main__":
    nums = [3, 1, 6, 8, 4]
    target = 24
    result = check_equal_partitions(nums, target)
    print(result)

C++完整代码如下：

#include <iostream>
#include <vector>
#include <set>
#include <functional>
#include <numeric>

using namespace std;

int gcd(int a, int b) {
    while (a != 0) {
        int temp = a;
        a = b % a;
        b = temp;
    }
    return b;
}

set<pair<int, int>> calc(const vector<int>& nums, int target) {
    set<pair<int, int>> result;

    function<void(int, int, int)> dfs = [&](int i, int a, int b) {
        if (a > target || b > target) return;
        if (i == nums.size()) {
            int g = gcd(a, b);
            result.insert({a / g, b / g}); // 最简分数
            return;
        }
        dfs(i + 1, a * nums[i], b);
        dfs(i + 1, a, b * nums[i]);
    };

    dfs(0, 1, 1);
    return result;
}

bool checkEqualPartitions(const vector<int>& nums, long long target) {
    // 计算总乘积
    long long total_product = 1;
    for (int x : nums) {
        total_product *= x;
    }

    if (total_product != target * target) {
        returnfalse;
    }

    int m = nums.size() / 2;
    auto set1 = calc(vector<int>(nums.begin(), nums.begin() + m), target);
    auto set2 = calc(vector<int>(nums.begin() + m, nums.end()), target);

    for (const auto& p : set1) {
        if (set2.find(p) != set2.end()) {
            returntrue;
        }
    }
    returnfalse;
}

int main() {
    vector<int> nums = {3, 1, 6, 8, 4};
    long long target = 24;
    bool result = checkEqualPartitions(nums, target);
    cout << (result ? "true" : "false") << endl;
    return0;
}