zzzrf：FB 还是比较爱考原题的
给定一个可能具有重复数字的列表，返回其所有可能的子集。
点此做题
样例 1：
输入：[0]
输出：
[
[],
[0]
]
样例 2：
输入：[1,2,2]
输出：
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
解题思路
- 这道题我们需要使用 dfs+回溯的方法来进行求解。
- 由于题目明确指出列表中可能有重复数字，所以我们在 dfs 的时候要进行剪枝。
算法
- 将数组进行升序排列。
- 定义一个递归方法 dfs，参数有：当前子集 subset，当前子集长度 k，返回结果 res 。 将当前子集添加到 res 中。 从 k 到 len(nums)-1 遍历索引 i 。 如果 i != k 并且 nums[i] == nums[i - 1]，说明 nums[i]是重复元素，所以我们跳过 nums[i]。 将 nums[i] 添加到当前子集 subset 。 进行下一层的递归搜索，继续向子集中添加元素，这时 k 要加一。 从 subset 中删除 nums[i]进行回溯。
举例分析
- 假设 nums = [1, 2, 2']，递归树如图所示。树每深一层，子集的长度就加一。每个节点都是满足条件的子集，需要记录到结果 res 中。
- 其中标叉的地方进行了剪枝。由于数组中有两个 2，所以如果两者在同一层，只保留第一个。
复杂度分析
- 时间复杂度：O(n∗2n)O(n∗2n)，其中 n 为 nums 的长度。生成所有子集，并复制到输出集合中。
- 空间复杂度：O(n∗2n)O(n∗2n)，其中 n 为 nums 的长度。存储所有子集，共 n 个元素，每个元素都有可能存在或者不存在。
代码
public class Solution {
/**
* @param nums: A set of numbers.
* @return: A list of lists. All valid subsets.
*/
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
// 排序
Arrays.sort(nums);
// dfs 搜索
Deque<Integer> subset = new ArrayDeque<>(nums.length);
dfs(nums, 0, subset, res);
return res;
}
private void dfs(int[] nums, int k, Deque<Integer> subset, List<List<Integer>> res) {
// 当前组合存入 res
res.add(new ArrayList<>(subset));
// 为 subset 新增一位元素
for (int i = k; i < nums.length; ++i) {
// 剪枝
if (i != k && nums[i] == nums[i - 1]){
continue;
}
subset.addLast(nums[i]);
// 下一层搜索
dfs(nums, i + 1, subset, res);
// 回溯
subset.removeLast();
}
}
}
hakunamatata11：课程概述 疫情下，从一名鹅厂高级产品经理一跃成为 Facebook E5 SDE，前期经历了 3 次面试失败，他都做了哪些准备才能一举拿下 offer，顺利上岸 内容介绍 算法面试如何突击 - 3 个月刷 600 道 行为面试到底考察啥 - 面试官都惊了 系统设计 - 找准方向其实也不难 Facebook 面试流程 - 原来是这…
Facebook 视频下载的 5 种最佳方法kevenlee：Facebook 上的视频怎么下下载？ Facebook （脸书）是大家比较熟知的国外社交媒体网站，里面有很多有趣的视频，很多人想将它们下载下来分享给朋友或家人观看但是网站没有提供直接下载的渠道，因此怎么下载 Facebook 上的视频一直是大家比较关注的问题,今天在这里我将分享五种 FB 视频下载方法，无论你使用 Android 还是 i…
LeetCode题解212. 单词搜索 II给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。示例:输入: words = ["oath","pea","eat","rain"] and bo…
LeetCode题解45.跳跃游戏 II给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。示例:输入: [2,3,1,1,4]输出: 2解释: 跳到最后一个位置的最小跳跃数是 2。 从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。说明:假设你总是可以到达数…
LeetCode题解140. 单词拆分 II批注： 由于"可以重复使用字典中的单词", 因此稍微难一点定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明：分隔时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入:s = "catsanddog"wordDict = […