Description#
Given an integer array nums of unique elements, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
Example 1:
Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input: nums = [0]
Output: [[],[0]]
Constraints:
1 <= nums.length <= 10-10 <= nums[i] <= 10- All the numbers of
nums are unique.
Solutions#
Solution 1: DFS (Backtracking)#
We design a function $dfs(i)$, which represents starting the search from the $i$th element of the array for all subsets. The execution logic of the function $dfs(i)$ is as follows:
- If $i = n$, it means the current search has ended. Add the current subset $t$ to the answer array $ans$, and then return.
- Otherwise, we can choose not to select the current element and directly execute $dfs(i + 1)$; or we can choose the current element, i.e., add the current element $nums[i]$ to the subset $t$, and then execute $dfs(i + 1)$. Note that we need to remove $nums[i]$ from the subset $t$ after executing $dfs(i + 1)$ (backtracking).
In the main function, we call $dfs(0)$, i.e., start searching all subsets from the first element of the array. Finally, return the answer array $ans$.
The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array. There are a total of $2^n$ subsets, and each subset takes $O(n)$ time to construct.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(i: int):
if i == len(nums):
ans.append(t[:])
return
dfs(i + 1)
t.append(nums[i])
dfs(i + 1)
t.pop()
ans = []
t = []
dfs(0)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private List<Integer> t = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0);
return ans;
}
private void dfs(int i) {
if (i == nums.length) {
ans.add(new ArrayList<>(t));
return;
}
dfs(i + 1);
t.add(nums[i]);
dfs(i + 1);
t.remove(t.size() - 1);
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> t;
function<void(int)> dfs = [&](int i) -> void {
if (i == nums.size()) {
ans.push_back(t);
return;
}
dfs(i + 1);
t.push_back(nums[i]);
dfs(i + 1);
t.pop_back();
};
dfs(0);
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func subsets(nums []int) (ans [][]int) {
t := []int{}
var dfs func(int)
dfs = func(i int) {
if i == len(nums) {
ans = append(ans, append([]int(nil), t...))
return
}
dfs(i + 1)
t = append(t, nums[i])
dfs(i + 1)
t = t[:len(t)-1]
}
dfs(0)
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| function subsets(nums: number[]): number[][] {
const ans: number[][] = [];
const t: number[] = [];
const dfs = (i: number) => {
if (i === nums.length) {
ans.push(t.slice());
return;
}
dfs(i + 1);
t.push(nums[i]);
dfs(i + 1);
t.pop();
};
dfs(0);
return ans;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| impl Solution {
fn dfs(i: usize, t: &mut Vec<i32>, res: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
if i == nums.len() {
res.push(t.clone());
return;
}
Self::dfs(i + 1, t, res, nums);
t.push(nums[i]);
Self::dfs(i + 1, t, res, nums);
t.pop();
}
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = Vec::new();
Self::dfs(0, &mut Vec::new(), &mut res, &nums);
res
}
}
|
Solution 2: Binary Enumeration#
We can also use the method of binary enumeration to get all subsets.
We can use $2^n$ binary numbers to represent all subsets of $n$ elements. For the current binary number $mask$, if the $i$th bit is $1$, it means that the $i$th element is selected, otherwise it means that the $i$th element is not selected.
The time complexity is $O(n \times 2^n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array. There are a total of $2^n$ subsets, and each subset takes $O(n)$ time to construct.
1
2
3
4
5
6
7
| class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
for mask in range(1 << len(nums)):
t = [x for i, x in enumerate(nums) if mask >> i & 1]
ans.append(t)
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
for (int mask = 0; mask < 1 << n; ++mask) {
List<Integer> t = new ArrayList<>();
for (int i = 0; i < n; ++i) {
if (((mask >> i) & 1) == 1) {
t.add(nums[i]);
}
}
ans.add(t);
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
for (int mask = 0; mask < 1 << n; ++mask) {
vector<int> t;
for (int i = 0; i < n; ++i) {
if (mask >> i & 1) {
t.emplace_back(nums[i]);
}
}
ans.emplace_back(t);
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
| func subsets(nums []int) (ans [][]int) {
n := len(nums)
for mask := 0; mask < 1<<n; mask++ {
t := []int{}
for i, x := range nums {
if mask>>i&1 == 1 {
t = append(t, x)
}
}
ans = append(ans, t)
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| function subsets(nums: number[]): number[][] {
const n = nums.length;
const ans: number[][] = [];
for (let mask = 0; mask < 1 << n; ++mask) {
const t: number[] = [];
for (let i = 0; i < n; ++i) {
if (((mask >> i) & 1) === 1) {
t.push(nums[i]);
}
}
ans.push(t);
}
return ans;
}
|
