前往
大廳
主題

LeetCode - 2597. The Number of Beautiful Subsets 解題心得

Not In My Back Yard | 2024-02-23 12:00:05 | 巴幣 0 | 人氣 46

題目連結:


題目意譯:
你被給定一個正整數陣列 nums,以及一正整數 k。

一個 nums 的子集合如果滿足不包含兩個整數有著絕對差值恰好為 k 的話,則其將視為是「美麗的」。

回傳陣列 nums 中美麗的非空子集合之數量。

一個 nums 的子集合為一個陣列,其可藉由刪除 nums 中若干個(可以是零個)元素而得到。兩個子集合是不一樣的,若且唯若兩者選擇刪除的元素之索引值有所不同。

限制:
1 ≦ nums.length ≦ 20
1 ≦ nums[i], k ≦ 1000



範例測資:
範例 1:
輸入: nums = [2,4,6], k = 2
輸出: 4
解釋: 陣列 nums 的美麗子集合為:[2] 、 [4] 、 [6] 、 [2, 6]。
可以證明陣列 [2,4,6] 之中只有 4 個美麗子集合。

範例 2:
輸入: nums = [1], k = 1
輸出: 1
解釋: 陣列 nums 的美麗子集合為:[1]。
可以證明陣列 [1] 之中只有 1 個美麗子集合。


解題思維:
直接窮舉出所有子集合並檢查即可。

以前(如這題)窮舉的時候是利用位元運算,這次的範例程式碼是使用深度優先搜尋(Depth First Search,DFS)來窮舉。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作