What is the core pattern in the 'Partition Array into Two Equal Product Subsets' problem?

The core pattern involves array manipulation combined with bit manipulation to enumerate all subsets, checking their products against a target.

How does bit manipulation help solve the Partition Array into Two Equal Product Subsets problem?

Bit manipulation allows you to efficiently generate subsets of the array, making it possible to check every possible partition for matching products.

What is the time complexity of solving the Partition Array into Two Equal Product Subsets problem?

The time complexity is exponential, primarily due to the need to generate and check all possible subsets of the array.

Can recursion be used to solve this problem? How?

Yes, recursion can be used to split the array into smaller subsets, and each partition's product can be recursively checked against the target value.

What is a common mistake in solving the Partition Array into Two Equal Product Subsets problem?

A common mistake is failing to apply early termination in recursion, causing the solution to check unnecessary subsets and exceed time limits.

#3566

Medium

auto_awesome数组·结合·位运算·操作

LeetCode 题解工作台

等积子集的划分方案

给你一个整数数组 nums ，其中包含的正整数互不相同，另给你一个整数 target 。请判断是否可以将 nums 分成两个非空、互不相交的子集，并且每个元素必须恰好属于一个子集，使得这两个子集中元素的乘积都等于 target 。如果存在这样的划分，返回 true ；否则…

数组位运算递归枚举

题目描述

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

lightbulb

解题思路

方法一：二进制枚举

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

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

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands how bit manipulation can help enumerate subsets efficiently.
question_mark
Candidate can optimize recursion using early termination to avoid unnecessary calculations.
question_mark
Candidate recognizes that the problem is inherently exponential in complexity.

warning

常见陷阱

外企场景

error
Incorrectly handling subsets, leading to redundant calculations or missing valid partitions.
error
Not using early termination, causing inefficient solutions that exceed time limits.
error
Forgetting to check if all elements are used in one subset, which violates the partition condition.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider larger arrays where performance optimization through pruning and dynamic programming may be necessary.
arrow_right_alt
Modify the problem by allowing subsets to contain zero or more elements instead of requiring non-empty subsets.
arrow_right_alt
Change the target value dynamically during runtime to test how the algorithm adapts.

help

常见问题

外企场景

继续练习

#3514 不同 XOR 三元组的数目 II #3483 不同三位偶数的数目 #3435 最短公共超序列的字母出现频率