|
…
|
||
|---|---|---|
| .. | ||
| README.md | ||
| README_EN.md | ||
| Solution.cpp | ||
| Solution.go | ||
| Solution.java | ||
| Solution.py | ||
| Solution.rs | ||
| Solution.ts | ||
| Solution2.cpp | ||
| Solution2.go | ||
| Solution2.java | ||
| Solution2.py | ||
| Solution2.rs | ||
| Solution2.ts | ||
README_EN.md
| comments | difficulty | edit_url | tags | |||
|---|---|---|---|---|---|---|
| true | Medium | https://github.com/doocs/leetcode/edit/main/solution/0000-0099/0078.Subsets/README_EN.md |
|
78. Subsets
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
numsare 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 subsettto the answer arrayans, 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 elementnums[i]to the subsett, and then executedfs(i + 1). Note that we need to removenums[i]from the subsettafter executingdfs(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.
Python3
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
Java
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);
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}
Rust
impl Solution {
fn dfs(i: usize, t: &mut Vec<i32>, ans: &mut Vec<Vec<i32>>, nums: &Vec<i32>) {
if i == nums.len() {
ans.push(t.clone());
return;
}
Self::dfs(i + 1, t, ans, nums);
t.push(nums[i]);
Self::dfs(i + 1, t, ans, nums);
t.pop();
}
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut ans = Vec::new();
Self::dfs(0, &mut Vec::new(), &mut ans, &nums);
ans
}
}
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.
Python3
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
Java
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;
}
}
C++
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;
}
};
Go
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
}
TypeScript
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;
}
Rust
impl Solution {
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let n = nums.len();
let mut ans = Vec::new();
for mask in 0..(1 << n) {
let mut t = Vec::new();
for i in 0..n {
if (mask >> i) & 1 == 1 {
t.push(nums[i]);
}
}
ans.push(t);
}
ans
}
}