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

九章小姐姐上岸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(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();
        }
    }
}

---

【福利放送时间】

Facebook 面试官帮你搞定 90%大厂高频动规题，帮你 14 天突击国内大厂面试最爱考的动态规划题型~

亮点

搜集近 3 年大厂 90%高频动规考题，你想进的，这里都有
字节跳动/网易/腾讯/微软/百度/快手/blibli/美团/拼多多/谷歌

搞定 7 大动规题型，吃透面试考点

区间型动态规划/双序列动态规划/划分型动态规划/坐标型动态规划/序列型动态规划/背包型动态规划/状态压缩动态规划

随时可以查看课程噢~
戳我现在 9 元即可秒杀

折扣码：AB3DF7 (使用方法：点击原价购买，然后在选择优惠框输入折扣码，即可 9 元获得全部课程）

转载：https://blog.csdn.net/JiuZhang_ninechapter/article/details/108712565