【重点】【DFS】【子集】78.子集
2023-12-18 19:37:31
法1:DFS
必须掌握的方法!!!
我们也可以用递归来实现子集枚举。
假设我们需要找到一个长度为 nnn 的序列 aaa 的所有子序列,代码框架是这样的:
void dfs(int cur, int n, LinkedList<Integer> tmp) {
if (cur == n) {
// 记录答案
// ...
return;
}
// 考虑选择当前位置
tmp.add(cur);
dfs(cur + 1, n, k);
tmp.removeLast();
// 考虑不选择当前位置
dfs(cur + 1, n, k);
}
答案如下:
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums.length == 0) {
return res;
}
LinkedList<Integer> tmp = new LinkedList<>();
dfs(nums, 0, tmp, res);
return res;
}
public void dfs(int[] nums, int startIndex, LinkedList<Integer> tmp, List<List<Integer>> res) {
if (startIndex == nums.length) {
res.add(new ArrayList<>(tmp));
return;
}
tmp.add(nums[startIndex]); // 选择当前值进行dfs
dfs(nums, startIndex + 1, tmp, res);
tmp.removeLast(); // 不选择当前值进行dfs
dfs(nums, startIndex + 1, tmp, res);
}
}
法2:动态规划
简单的dp问题。
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums.length == 0) {
return res;
}
res.add(new ArrayList<>());
for (int i = 0; i < nums.length; ++i) {
int size = res.size();
for (int k = 0; k < size; ++k) {
List<Integer> newList = new ArrayList<>(res.get(k));
newList.add(nums[i]);
res.add(newList);
}
}
return res;
}
}
文章来源:https://blog.csdn.net/Allenlzcoder/article/details/135069332
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!