• Leetcode 3566. Partition Array into Two Equal Product Subsets
  • 1. 解題思路
  • 2. 代碼實現

• 題目鏈接：3566. Partition Array into Two Equal Product Subsets

1. 解題思路

這一題我的實現還是比較暴力的，首先顯而易見的，若要滿足題目要求，則給出的數組的所有元素的乘積必然是target的平方，因此，我們可以快速由此判斷該數組是否可分。

然后，在滿足上述條件的前提下，我們就是要找到若干個元素使之乘積恰好為target，這個的話我們可以通過一個動態規劃進行實現。

2. 代碼實現

給出python代碼實現如下：

class Solution:def checkEqualPartitions(self, nums: List[int], target: int) -> bool:prod = 1for num in nums:prod *= numif prod != target * target:return Falsen = len(nums)@lru_cache(None)def dp(idx, tgt):if tgt == 1:return Trueif idx >= n:return Falseif tgt % nums[idx] == 0:return dp(idx+1, tgt) or dp(idx+1, tgt // nums[idx])else:return dp(idx+1, tgt)return dp(0, target)

提交代碼評測得到：耗時7ms，占用內存18.5MB。