LeetCode-78. 子集
问题地址
LeetCode78. 子集
问题描述
规则
- 给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。
说明
- 解集不能包含重复的子集。
示例
- 示例一:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
解析
解题思路
- 每个元素都有两个选项,选择、不选择;
- 一个子树就是一个递归调用,对当前枚举的数,选和不选可以分出两个分支,分别对应两个递归的子调用,在子调用中,考察下一个数。
- 当 inx 越界(
inx == nums.length
)时,就把生成的子集加入解中,结束当前递归分支。 - 我们找到一个子集结束递归,要撤销当前的选择(把当前选的数从 list 中删掉),回到选择前的状态,做另一个选择——不选当前的数,往下递归,继续生成子集。
数据操作分析
- 判断当前指针是否等于给定序列的长度,若
inx == nums.length
则将当前子集假如到解中,并结束当前递归; - 若 inx
则将当前元素加入到当前子集中,并继续下一个数选择; - 回溯,撤销当前的选择回到选择前的状态,不选当前数继续往下递归;
复杂度分析
- 时间复杂度
- 空间复杂度
编码实现
public class LeetCode0078_Subsets {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> tmp = new ArrayList<>();
dfs(ans, tmp, 0, nums);
return ans;
}
private void dfs(List<List<Integer>> ans, List<Integer> tmp, int inx, int[] nums) {
if (inx == nums.length) {
ans.add(new ArrayList<>(tmp));
return;
}
tmp.add(nums[inx]);
dfs(ans, tmp, inx + 1, nums);
tmp.remove(tmp.size() - 1);
dfs(ans, tmp, inx + 1, nums);
}
}
官方解法
方法一:迭代法实现子集枚举
思路:
-
记原序列中元素的总数为 n。原序列中的每个数字 a_i 的状态可能有两种,即「在子集中」和「不在子集中」。我们用 1 表示「在子集中」,0 表示不在子集中,那么每一个子集可以对应一个长度为 n 的 0/1 序列,第 i 位表示 a_i 是否在子集中。例如,n = 3 ,a ={5, 2, 9 } 时:
0/1 序列 子集 0/1 序列对应的二进制数 000 {} 0 001 {9} 1 010 {2} 2 011 {2,9} 3 100 {5} 4 101 {5,9} 5 110 {5,2} 6 111 {5,2,9} 7 -
可以发现 0/1 序列对应的二进制数正好从 0 到 2^n – 1。我们可以枚举 {\rm mask} \in [0, 2^n – 1],\rm mask 的二进制表示是一个 0/1 序列,我们可以按照这个 0/1 序列在原集合当中取数。当我们枚举完所有 2^n 个 \rm mask,我们也就能构造出所有的子集。
复杂度分析:
- 时间复杂度:O(n×2^n )。一共 2^n 个状态,每种状态需要 O(n) 的时间来构造子集。
- 空间复杂度:O(n)。即构造子集使用的临时数组 t 的空间代价。
编码实现
class Solution {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
int n = nums.length;
for (int mask = 0; mask < (1 << n); ++mask) {
t.clear();
for (int i = 0; i < n; ++i) {
if ((mask & (1 << i)) != 0) {
t.add(nums[i]);
}
}
ans.add(new ArrayList<Integer>(t));
}
return ans;
}
}
方法一:递归法实现子集枚举
思路:
- 我们也可以用递归来实现子集枚举。假设我们需要找到一个长度为 nn 的序列 aa 的所有子序列,代码框架是这样的:
vector<int> t;
void dfs(int cur, int n) {
if (cur == n) {
// 记录答案
// ...
return;
}
// 考虑选择当前位置
t.push_back(cur);
dfs(cur + 1, n, k);
t.pop_back();
// 考虑不选择当前位置
dfs(cur + 1, n, k);
}
- 上面的代码中,{\rm dfs(cur,} n) 参数表示当前位置是 \rm cur,原序列总长度为 n。原序列的每个位置在答案序列中的状态有被选中和不被选中两种,我们用 \rm t 数组存放已经被选出的数字。在进入 {\rm dfs(cur,} n) 之前 \rm [0, cur – 1] 位置的状态是确定的,而 [{\rm cur}, n – 1] 内位置的状态是不确定的,{\rm dfs(cur,} n) 需要确定 \rm cur 位置的状态,然后求解子问题 {\rm dfs(cur + 1}, n)。对于 \rm cur 位置,我们需要考虑 a[{\rm cur}] 取或者不取,如果取,我们需要把 a[{\rm cur}] 放入一个临时的答案数组中(即上面代码中的 \rm t),再执行 {\rm dfs(cur + 1}, n),执行结束后需要对 \rm t 进行回溯;如果不取,则直接执行 {\rm dfs(cur + 1}, n)。在整个递归调用的过程中,\rm cur 是从小到大递增的,当 \rm cur 增加到 n 的时候,记录答案并终止递归。可以看出二进制枚举的时间复杂度是 O(2^n)。
复杂度分析:
- 时间复杂度:O(n×2^n )。一共 2^n 个状态,每种状态需要 O(n) 的时间来构造子集。
- 空间复杂度:O(n)。临时数组 t 的空间代价是 O(n),递归时栈空间的代价为 O(n)。
编码实现
class Solution {
List<Integer> t = new ArrayList<Integer>();
List<List<Integer>> ans = new ArrayList<List<Integer>>();
public List<List<Integer>> subsets(int[] nums) {
dfs(0, nums);
return ans;
}
public void dfs(int cur, int[] nums) {
if (cur == nums.length) {
ans.add(new ArrayList<Integer>(t));
return;
}
t.add(nums[cur]);
dfs(cur + 1, nums);
t.remove(t.size() - 1);
dfs(cur + 1, nums);
}
}
精彩评论
跳转地址1:二进制位,逐个枚举,DFS 三种思路,9+ 种以上的写法
思路一:
- 集合的每个元素,都有可以选或不选,用二进制和位运算,可以很好的表示。
编码实现
public static List<List<Integer>> binaryBit(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
for (int i = 0; i < (1 << nums.length); i++) {
List<Integer> sub = new ArrayList<Integer>();
for (int j = 0; j < nums.length; j++)
if (((i >> j) & 1) == 1) sub.add(nums[j]);
res.add(sub);
}
return res;
}
思路二:
- 逐个枚举,空集的幂集只有空集,每增加一个元素,让之前幂集中的每个集合,追加这个元素,就是新增的子集。
编码实现
/**
* 循环枚举
*/
public static List<List<Integer>> enumerate(int[] nums) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
res.add(new ArrayList<Integer>());
for (Integer n : nums) {
int size = res.size();
for (int i = 0; i < size; i++) {
List<Integer> newSub = new ArrayList<Integer>(res.get(i));
newSub.add(n);
res.add(newSub);
}
}
return res;
}
/**
* 递归枚举
*/
public static void recursion(int[] nums, int i, List<List<Integer>> res) {
if (i >= nums.length) return;
int size = res.size();
for (int j = 0; j < size; j++) {
List<Integer> newSub = new ArrayList<Integer>(res.get(j));
newSub.add(nums[i]);
res.add(newSub);
}
recursion(nums, i + 1, res);
}
思路三:
- 集合中每个元素的选和不选,构成了一个满二叉状态树,比如,左子树是不选,右子树是选,从根节点、到叶子节点的所有路径,构成了所有子集。可以有前序、中序、后序的不同写法,结果的顺序不一样。本质上,其实是比较完整的中序遍历。
编码实现
/**
* DFS,前序遍历
*/
public static void preOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
if (i >= nums.length) return;
// 到了新的状态,记录新的路径,要重新拷贝一份
subset = new ArrayList<Integer>(subset);
// 这里
res.add(subset);
preOrder(nums, i + 1, subset, res);
subset.add(nums[i]);
preOrder(nums, i + 1, subset, res);
}
/**
* DFS,中序遍历
*/
public static void inOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
if (i >= nums.length) return;
subset = new ArrayList<Integer>(subset);
inOrder(nums, i + 1, subset, res);
subset.add(nums[i]);
// 这里
res.add(subset);
inOrder(nums, i + 1, subset, res);
}
/**
* DFS,后序遍历
*/
public static void postOrder(int[] nums, int i, ArrayList<Integer> subset, List<List<Integer>> res) {
if (i >= nums.length) return;
subset = new ArrayList<Integer>(subset);
postOrder(nums, i + 1, subset, res);
subset.add(nums[i]);
postOrder(nums, i + 1, subset, res);
// 这里
res.add(subset);
}
- 也可以左子树是选,右子树是不选,相当于,也可以前序、中序、后序的不同写法。程序实现上,需要用一个栈,元素入栈遍历左子树,(最近入栈的那个)元素出栈,遍历右子树。
public static void newPreOrder(int[] nums, int i, LinkedList<Integer> stack, List<List<Integer>> res) {
if (i >= nums.length) return;
stack.push(nums[i]);
// 这里
res.add(new ArrayList<Integer>(stack));
newPreOrder(nums, i + 1, stack, res);
stack.pop();
newPreOrder(nums, i + 1, stack, res);
}
public static void backtrack(int[] nums, int i, List<Integer> sub, List<List<Integer>> res) {
for (int j = i; j < nums.length; j++) {
if (j > i && nums[j] == nums[j - 1]) continue;
sub.add(nums[j]);
res.add(new ArrayList<Integer>(sub));
backtrack(nums, j + 1, sub, res);
sub.remove(sub.size() - 1);
}
}
跳转地址2:78. 子集:【回溯搜索法】经典题目详解!
思路
- 求子集问题和 求组合组合和分割问题又不一样了, 如何把 子集问题、组合问题、分割问题都抽象为一棵树的话,那么组合问题和分割问题都是找树的叶子节点,而子集问题是找树的所有节点!取子集也是,其实也是一种组合位置,因为它的集合是无序的,子集{1,2} 和 子集{2,1}是一样的。 那么既然是无序,写回溯算法的时候,for就要从startIndex开始,而不是从0开始!那有同学问题,什么时候,for可以从0开始,求排列问题的时候,就要从0开始,因为集合是有序的,{1, 2} 和{2, 1}是两个集合。以示例中nums = [1,2,3]为例把求子集抽象为树型结构,如下:
- 从图中,可以看出,遍历这个树的时候,把所有节点都记录下来,就是要求的子集。来看一下我总结的回溯模板来:
backtracking() {
if (终止条件) {
存放结果;
}
for (选择:选择列表(可以想成树中节点孩子的数量)) {
递归,处理节点;
backtracking();
回溯,撤销处理结果
}
}
- 首先是终止条件,终止条件,就是startIndex已经大于数组的长度了,就是终止了,代码如下:
if (startIndex >= nums.size()) {
return;
}
- 但是,要明确的是,求取子集问题,其实没有必要加终止条件,因为子集就是要遍历整个一棵树,不需要任何剪枝!大家一会看到下面整体代码的时候就知道了。
- 然后就是看如何写for循环,因为求子集也是无序的,所以for循环要从startIndex开始! 代码如下:
for (int i = startIndex; i < nums.size(); i++) {}
- 接下来就是递归与回溯,定一个vector path,用来收集子集的元素,在回溯的时候还要弹出,backtracking每次调用自己的时候,记着要从i+1 开始,代码如下:
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
- 重点代码分析完之后,整体代码如下:
- 可以发现我在backtracking里并没有写终止条件,因为本来我们就要遍历整颗树。
- 有的同学可能担心会不会无限递归? 并不会,因为每次递归的下一层就是从i+1开始的。
编码实现
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};
跳转地址3:回溯算法
思路一:库函数
编码实现
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
for i in range(len(nums)+1):
for tmp in itertools.combinations(nums, i):
res.append(tmp)
return res
思路二:迭代
编码实现
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for i in nums:
res = res + [[i] + num for num in res]
return res
思路三:递归(回溯算法)
编码实现
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(0, nums, res, new ArrayList<Integer>());
return res;
}
private void backtrack(int i, int[] nums, List<List<Integer>> res, ArrayList<Integer> tmp) {
res.add(new ArrayList<>(tmp));
for (int j = i; j < nums.length; j++) {
tmp.add(nums[j]);
backtrack(j + 1, nums, res, tmp);
tmp.remove(tmp.size() - 1);
}
}
}
类似题目
- 39.组合总和
- 40. 组合总和 II
- 46. 全排列
- 47. 全排列 II
- 78. 子集
-
这类题目都是同一类型的,用回溯算法!其实回溯算法关键在于: 不合适就退回上一步然后通过约束条件, 减少时间复杂度.
- 大家可以从下面的解法找出一点感觉!
//78子集
class Solution:
def subsets(self, nums):
if not nums:
return []
res = []
n = len(nums)
def helper(idx, temp_list):
res.append(temp_list)
for i in range(idx, n):
helper(i + 1, temp_list + [nums[i]])
helper(0, [])
return res
//90. 子集 II
class Solution(object):
def subsetsWithDup(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return []
n = len(nums)
res = []
nums.sort()
# 思路1
def helper1(idx, n, temp_list):
if temp_list not in res:
res.append(temp_list)
for i in range(idx, n):
helper1(i + 1, n, temp_list + [nums[i]])
# 思路2
def helper2(idx, n, temp_list):
res.append(temp_list)
for i in range(idx, n):
if i > idx and nums[i] == nums[i - 1]:
continue
helper2(i + 1, n, temp_list + [nums[i]])
helper2(0, n, [])
return res
//46. 全排列
class Solution(object):
def permute(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return
res = []
n = len(nums)
visited = [0] * n
def helper1(temp_list,length):
if length == n:
res.append(temp_list)
for i in range(n):
if visited[i] :
continue
visited[i] = 1
helper1(temp_list+[nums[i]],length+1)
visited[i] = 0
def helper2(nums,temp_list,length):
if length == n:
res.append(temp_list)
for i in range(len(nums)):
helper2(nums[:i]+nums[i+1:],temp_list+[nums[i]],length+1)
helper1([],0)
return res
//47. 全排列 II
class Solution(object):
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
if not nums:
return []
nums.sort()
n = len(nums)
visited = [0] * n
res = []
def helper1(temp_list, length):
# if length == n and temp_list not in res:
# res.append(temp_list)
if length == n:
res.append(temp_list)
for i in range(n):
if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]):
continue
visited[i] = 1
helper1(temp_list + [nums[i]], length + 1)
visited[i] = 0
def helper2(nums, temp_list, length):
if length == n and temp_list not in res:
res.append(temp_list)
for i in range(len(nums)):
helper2(nums[:i] + nums[i + 1:], temp_list + [nums[i]], length + 1)
helper1([],0)
# helper2(nums, [], 0)
return res
//39.组合总和
class Solution(object):
def combinationSum(self, candidates, target):
"""
:type candidates: List[int]
:type target: int
:rtype: List[List[int]]
"""
if not candidates:
return []
if min(candidates) > target:
return []
candidates.sort()
res = []
def helper(candidates, target, temp_list):
if target == 0:
res.append(temp_list)
if target < 0:
return
for i in range(len(candidates)):
if candidates[i] > target:
break
helper(candidates[i:], target - candidates[i], temp_list + [candidates[i]])
helper(candidates,target,[])
return res
//40. 组合总和 II
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if not candidates:
return []
candidates.sort()
n = len(candidates)
res = []
def backtrack(i, tmp_sum, tmp_list):
if tmp_sum == target:
res.append(tmp_list)
return
for j in range(i, n):
if tmp_sum + candidates[j] > target : break
if j > i and candidates[j] == candidates[j-1]:continue
backtrack(j + 1, tmp_sum + candidates[j], tmp_list + [candidates[j]])
backtrack(0, 0, [])
return res