※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: https://leetcode.com/problems/the-number-of-beautiful-subsets/description
: 2597. The Number of Beautiful Subsets
: 給你一個陣列表示一個集合和一個數字k，求出美麗子集數量，美麗子集是一個非空子集合
: ，所有子集元素彼此相差絕對值不會等於k。
: 思路：
: 1.回溯法，每次把元素加到當前子集前先檢查是否包含+k或-k，沒有才加。
: py code:
: --------------------------------------
: class Solution:
: def beautifulSubsets(self, nums: List[int], k: int) -> int:
: self.res = 0
: n = len(nums)
: mp = defaultdict(int)
: def dfs(start: int):
: if mp:
: self.res += 1
: for i in range(start, n):
: if mp[nums[i] - k] <= 0 and mp[nums[i] + k] <= 0:
: mp[nums[i]] += 1
: dfs(i + 1)
: mp[nums[i]] -= 1
: dfs(0)
: return self.res
: --------------------------------------
思路差不多 不過我速度慢很多 應該是檢查k那邊有差
Python Code:
class Solution:
def beautifulSubsets(self, nums: List[int], k: int) -> int:
def backtrack(state,start):
nonlocal res
for i in range(start,len(nums)):
if check(state,nums[i]):
state.append(nums[i])
backtrack(state,i+1)
state.pop()
if state:
res += 1
def check(state,num):
for n in state:
if num - n == k or num - n == -k:
return False
return True
res = 0
backtrack([],0)
return res
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.119.235.6 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1716433461.A.2B7.html