? ? ? ?題目描述：

? ? ? ?給定一組不含重復(fù)元素的整數(shù)數(shù)組 nums，返回該數(shù)組所有可能的子集（冪集）。
? ? ? ?說明：解集不能包含重復(fù)的子集。
? ? ? ?示例:
? ? ? ?輸入: nums = [1,2,3]
? ? ? ?輸出:
? ? ? ?[
? ? ? ? ? [3],
? ? ? ? ? [1],
? ? ? ? ? [2],
? ? ? ? ? [1,2,3],
? ? ? ? ? [1,3],
? ? ? ? ? [2,3],
? ? ? ? ? [1,2],
? ? ? ? ? []
? ? ?]?

先看一張力扣上的圖:

可以通過對應(yīng)二進制位是否為1，判斷是否需要該數(shù)，由表格可推得總的情況總數(shù)是：0~z^n-1

//子集枚舉 //按位&：僅當兩個都為1時才位1 func subsets(nums []int) (ans [][]int) {n := len(nums)//運算符優(yōu)先級<<比<大//1<<n 表示結(jié)果的個數(shù)for mask := 0; mask < 1<<n; mask++ {set := []int{}for i, v := range nums {//運算符優(yōu)先級>>比&(按位&)大//mask>>i &1 判斷第i位是不是1if mask>>i &1 > 0 {set = append(set, v)}}ans = append(ans, append([]int(nil), set...))}return }

代碼的主要思想在這段：mask>>i &1 > 0? ? 意思是判斷第i位是不是1，右移i個和1按位&。看上圖可知道，判斷該位是否為1，可以知道是否需要該數(shù)，如果大于1，則將其放到數(shù)組里。

時間復(fù)雜度：O(n*2^n)

空間復(fù)雜度：O(n)

?

看下遞歸的解決方案：

func subsets(nums []int) (ans [][]int) {set := []int{}var dfs func(int)dfs = func(cur int) {if cur == len(nums) {ans = append(ans, append([]int(nil), set...))return}set = append(set, nums[cur])dfs(cur + 1)set = set[:len(set)-1]dfs(cur + 1)}dfs(0)return }

每個數(shù)可以選擇取還是不取

時間空間復(fù)雜度同上

?

參考地址：https://leetcode-cn.com/problems/subsets/solution/zi-ji-by-leetcode-solution/

?

?

?

?

總結(jié)

以上是生活随笔為你收集整理的巧妙异或思路解子集问题，面试官叫绝的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。