ETH官方钱包

前往
大廳
主題

LeetCode - 90. Subsets II 解題心得

Not In My Back Yard | 2022-01-04 00:00:01 | 巴幣 2 | 人氣 264

題目連結:


題目意譯:
給定一可能包含重複元素之整數陣列 nums,回傳所有可能的子集合(即冪集(Power Set))。

答案集合不得包含重複的子集合。可按任意順序回傳答案。

限制:
1 ≦ nums.length ≦ 10
-10 ≦ nums[i] ≦ 10



範例測資:
範例 1:
輸入: nums = [1,2,2]
輸出: [[],[1],[1,2],[1,2,2],[2],[2,2]]

範例 2:
輸入: nums = [0]
輸出: [[],[0]]


解題思維:
類似昨天的作法。不過因為陣列中的元素可能重複,所以我們需要先將 nums 排序,這樣窮舉的時候才不會出現以下情況:
nums = [3,1,3],"011" 會得到子集合 [3,1] 、 "110" 會得到子集合 [1,3]。這兩個子集合相同,但是內部的元素排列不相同,這樣判斷兩者是否真的相同比較難比較。

排序後按照昨天的作法,然後每生成一個新的子集合後判斷其是否已存在於答案陣列中。如果是就不加入於答案中;反之則加入於其中。

最後的答案陣列即為所求。




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

創作回應

更多創作