題目連結:
題目意譯:
給定一個相異整數之陣列 nums,回傳所有可能的子集合(即冪集(Power Set))。
答案集合不得包含重複的子集合。可按任意順序回傳答案。
限制:
1 ≦ nums.length ≦ 10
-10 ≦ nums[i] ≦ 10
nums 中所有數字皆相異。
範例測資:
範例 1:
輸入: nums = [1,2,3]
輸出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
範例 2:
輸入: nums = [0]
輸出: [[],[0]]
解題思維:
假設 nums 中有 X 個元素,可以看到其冪集應當有 2 ^ X 個元素。而我們恰好可以利用二進位數字來窮舉每個元素挑與不挑之狀態。
例如 nums = [2,3,1] 因此 X = 3。而二進位數字 "101" 代表著要挑第 2 、 0 個元素也就是得到 [2,1] 、 "001" 代表著要挑第 0 個元素(陣列索引值時常從 0 開始,而最右邊的位元剛好是 2 ^ 0)即 [1] 等等。
因此我們從 i = 0 跑到 2 ^ X - 1,然後對於每個 i 值得出其所代表的子集合。將這些子集合包成一個陣列即是所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。