題目連結:
題目意譯:
給定一可能包含重複元素之整數陣列 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]。這兩個子集合相同,但是內部的元素排列不相同,這樣判斷兩者是否真的相同比較難比較。
排序後按照昨天的作法,然後每生成一個新的子集合後判斷其是否已存在於答案陣列中。如果是就不加入於答案中;反之則加入於其中。
最後的答案陣列即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。