幂集。编写一种方法,返回某集合的所有子集。集合中不包含重复的元素。
说明:解集不能包含重复的子集。
示例:
输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
方法一:递归枚举
我们设计一个递归函数
当前枚举到的元素下标为
时间复杂度
方法二:二进制枚举
我们可以将方法一中的递归过程改写成迭代的形式,即使用二进制枚举的方法来枚举所有的子集。
我们可以使用 mask
的第
时间复杂度
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def dfs(u, t):
if u == len(nums):
ans.append(t[:])
return
dfs(u + 1, t)
t.append(nums[u])
dfs(u + 1, t)
t.pop()
ans = []
dfs(0, [])
return ans
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
for mask in range(1 << len(nums)):
t = []
for i, v in enumerate(nums):
if (mask >> i) & 1:
t.append(v)
ans.append(t)
return ans
class Solution {
private List<List<Integer>> ans = new ArrayList<>();
private int[] nums;
public List<List<Integer>> subsets(int[] nums) {
this.nums = nums;
dfs(0, new ArrayList<>());
return ans;
}
private void dfs(int u, List<Integer> t) {
if (u == nums.length) {
ans.add(new ArrayList<>(t));
return;
}
dfs(u + 1, t);
t.add(nums[u]);
dfs(u + 1, t);
t.remove(t.size() - 1);
}
}
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;
}
}
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> t;
dfs(0, nums, t, ans);
return ans;
}
void dfs(int u, vector<int>& nums, vector<int>& t, vector<vector<int>>& ans) {
if (u == nums.size()) {
ans.push_back(t);
return;
}
dfs(u + 1, nums, t, ans);
t.push_back(nums[u]);
dfs(u + 1, nums, t, ans);
t.pop_back();
}
};
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> t;
int n = nums.size();
for (int mask = 0; mask < 1 << n; ++mask)
{
t.clear();
for (int i = 0; i < n; ++i)
{
if ((mask >> i) & 1)
{
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};
func subsets(nums []int) [][]int {
var ans [][]int
var dfs func(u int, t []int)
dfs = func(u int, t []int) {
if u == len(nums) {
ans = append(ans, append([]int(nil), t...))
return
}
dfs(u+1, t)
t = append(t, nums[u])
dfs(u+1, t)
t = t[:len(t)-1]
}
var t []int
dfs(0, t)
return ans
}
func subsets(nums []int) [][]int {
var ans [][]int
n := len(nums)
for mask := 0; mask < 1<<n; mask++ {
t := []int{}
for i, v := range nums {
if ((mask >> i) & 1) == 1 {
t = append(t, v)
}
}
ans = append(ans, t)
}
return ans
}
function subsets(nums: number[]): number[][] {
const res = [[]];
nums.forEach(num => {
res.forEach(item => {
res.push(item.concat(num));
});
});
return res;
}
function subsets(nums: number[]): number[][] {
const n = nums.length;
const res = [];
const list = [];
const dfs = (i: number) => {
if (i === n) {
res.push([...list]);
return;
}
list.push(nums[i]);
dfs(i + 1);
list.pop();
dfs(i + 1);
};
dfs(0);
return res;
}
impl Solution {
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let n = nums.len();
let mut res: Vec<Vec<i32>> = vec![vec![]];
for i in 0..n {
for j in 0..res.len() {
res.push(vec![..res[j].clone(), vec![nums[i]]].concat());
}
}
res
}
}
impl Solution {
fn dfs(nums: &Vec<i32>, i: usize, res: &mut Vec<Vec<i32>>, list: &mut Vec<i32>) {
if i == nums.len() {
res.push(list.clone());
return;
}
list.push(nums[i]);
Self::dfs(nums, i + 1, res, list);
list.pop();
Self::dfs(nums, i + 1, res, list);
}
pub fn subsets(nums: Vec<i32>) -> Vec<Vec<i32>> {
let mut res = vec![];
Self::dfs(&nums, 0, &mut res, &mut vec![]);
res
}
}