算法的經典例題?給定一組不含重複元素的整數數組 nums，返回該數組所有可能的子集（幂集），下面我們就來聊聊關于算法的經典例題?接下來我們就一起去了解一下吧!

算法的經典例題

給定一組不含重複元素的整數數組 nums，返回該數組所有可能的子集（幂集）。

說明：解集不能包含重複的子集。

示例:

輸入: nums = [1,2,3]

輸出:

[ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

這道題是一道典型的考驗遞歸算法的題目，根據題目可以想到，[1,2,3]的子集是[1,2]裡面所有的子集和[1,2]裡面所有子集和3的組合加上[3]。

var subsets = function(nums) { // 長度為1時結束遞歸 if (nums.length === 1) { return [[], [nums[0]]] } // 如果初始的長度就為0，則直接返回[[]] if (nums.length === 0) { return [[]] } // 取出最後一個數 const nowValue = nums.pop() // 剩下的數字做遞歸，找出剩下數字的所有子集 const childSubs = subsets(nums) // 對所有子集的長度賦值，因為這裡會在原數組上做修改，所以先記錄了原數組的長度 const subsLength = childSubs.length // 循環遍曆所有子集 for(let i = 0; i < subsLength; i ) { // 插入當前數和所有子集組合生成的新的子集 childSubs.push([...childSubs[i], nowValue]) } // 返回結果 return childSubs };

時間複雜度 O(N*2^N)，生成所有子集，并複制到輸出結果中。

空間複雜度 O(N*2^N)，這是子集的數量。

對于給定的任意元素，它在子集中有兩種情況，存在或者不存在（對應二進制中的 0 和 1）。因此，NN 個數字共有 2^N2N 個子集。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!