Partition Array Into Two Equal Product Subsets

3566. 等积子集的划分方案

算法

用两个变量 mul1 和 mul2 分别表示当前两个子集的乘积
从索引 0 开始枚举每个元素，将其放入 mul1 或 mul2
剪枝：如果任何一边的乘积已经超过 target，当前方案结束
若遍历到末尾，判断是否两个乘积都等于 target

复杂度分析

时间复杂度：O(2^n)，每个数都有两种放法，共 2^n 种可能
空间复杂度：O(n)，递归栈深度最多为 n

C++ 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
  // DFS 枚举当前第 i 个数放到哪个子集（乘积为 mul1 或 mul2）
  bool dfs(std::vector<int>& nums, int i, long long mul1, long long mul2, long long target)
  {
    if (mul1 > target || mul2 > target) {
      return false; // 剪枝：乘积已经超过目标
    }
    if (i == nums.size()) {
      return mul1 == target && mul2 == target; // 判断是否两个子集都达成目标乘积
    }
    // 尝试将当前数 nums[i] 加入 mul1 或 mul2 子集中
    return dfs(nums, i + 1, mul1 * nums[i], mul2, target) ||
           dfs(nums, i + 1, mul1, mul2 * nums[i], target);
  }

  bool checkEqualPartitions(vector<int>& nums, long long target) {
    return dfs(nums, 0, 1, 1, target); // 初始两个子集乘积为 1
  }
};

Python 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def dfs(self, nums: List[int], i: int, mul1: int, mul2: int, target: int) -> bool:
      if mul1 > target or mul2 > target:
        return False
      if i == len(nums):
        return mul1 == target and mul2 == target
      return self.dfs(nums, i + 1, mul1 * nums[i], mul2, target) or self.dfs(nums, i + 1, mul1, mul2 * nums[i], target)

    def checkEqualPartitions(self, nums: List[int], target: int) -> bool:
      return self.dfs(nums, 0, 1, 1, target)

Go 代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


func dfs(nums []int, i int, mul1 int, mul2 int, target int) bool {
  if mul1 > target || mul2 > target {
    return false
  }
  if i == len(nums) {
    return mul1 == target && mul2 == target
  }
  return dfs(nums, i + 1, mul1 * nums[i], mul2, target) || dfs(nums, i + 1, mul1, mul2 * nums[i], target)
}

func checkEqualPartitions(nums []int, target int64) bool {
  return dfs(nums, 0, 1, 1, int(target))
}