3333 - 在选择该元素的情况下，继续递归考虑下一个元素。
3434 - 进行回溯，撤销选择该元素。即从当前子集数组 ` sub_set ` 中移除之前添加的元素。
3535
36+ ### 思路 1 ：回溯算法代码
37+
38+ ``` Python
39+ class Solution :
40+ def backtrack (self sub_sets , nums , sub_set , start ):
41+ sub_sets.append(sub_set[:])
42+
43+ for i in range (start, len (nums)):
44+ sub_set.append(nums[i])
45+ self .backtrack(sub_sets, nums, sub_set, i + 1 )
46+ sub_set.pop()
47+ return sub_sets
48+
49+ def subsets (self nums : List[int ]) -> List[List[int ]]:
50+ if not nums:
51+ return []
52+ sub_sets = []
53+ return self .backtrack(sub_sets, nums, [], 0 )
54+ ```
55+
3656### 思路 2：二进制枚举
3757
3858对于一个元素个数为 ` n ` 的集合 ` nums ` 来说，每一个位置上的元素都有选取和未选取两种状态。我们可以用数字 ` 1 ` 来表示选取该元素，用数字 ` 0 ` 来表示不选取该元素。
6888
6989- 对于长度为 ` 5 ` 的集合 ` nums ` 来说，只需要枚举 $0 \sim 2^n - 1$（共 $2^n$ 种情况），即可得到所有的子集。
7090
71- ## 代码
72-
73- ### 思路 1 ：回溯算法代码
74-
75- ``` Python
76- class Solution :
77- def backtrack (self sub_sets , nums , sub_set , start ):
78- sub_sets.append(sub_set[:])
79-
80- for i in range (start, len (nums)):
81- sub_set.append(nums[i])
82- self .backtrack(sub_sets, nums, sub_set, i + 1 )
83- sub_set.pop()
84- return sub_sets
85-
86- def subsets (self nums : List[int ]) -> List[List[int ]]:
87- if not nums:
88- return []
89- sub_sets = []
90- return self .backtrack(sub_sets, nums, [], 0 )
91- ```
9291
9392### 思路 2：二进制枚举代码
9493
@@ -100,7 +99,7 @@ class Solution:
10099 for i in range (1 << n): # 枚举 0 ~ 2^n - 1
101100 sub_set = [] # sub_set 用于保存当前子集
102101 for j in range (n): # 枚举第 i 位元素
103- if i >> j & 1 : # 如果第 i 为元素对应二进制位删改为 1，则表示选取该元素
102+ if i >> j & 1 : # 如果第 i 为元素对应二进制位为 1，则表示选取该元素
104103 sub_set.append(nums[j]) # 将选取的元素加入到子集 sub_set 中
105104 sub_sets.append(sub_set) # 将子集 sub_set 加入到所有子集数组 sub_sets 中
106105 return sub_sets # 返回所有子集
0 commit comments