Facebook 程序媛分享面试真题（手写版题解噢）

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

如果想在 V2EX 获得更好的推广效果，欢迎了解 PRO 会员机制：
pro/about

这是一个创建于 2042 天前的主题，其中的信息可能已经有所发展或是发生改变。

小姐姐上岸 Facebook，分享一题面试中遇到的题，Facebook 还是比较爱考原题的。

给定一个可能具有重复数字的列表，返回其所有可能的子集。

点此做题

样例 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(n2n)O(n2n)，其中 n 为 nums 的长度。生成所有子集，并复制到输出集合中。
空间复杂度：O(n2n)O(n2n)，其中 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(); } } }