題目連結:
題目意譯:
你被給定一個正整數陣列 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)來窮舉。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。