LeetCode 90 子集 II（Java 标准回溯算法 天然无添加）

本文主要是介绍LeetCode 90 子集 II（Java 标准回溯算法 天然无添加），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目：

这里是引用

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例2：

输入：nums = [0]
输出：[[],[0]]

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10

解题代码：

class Solution {
	// 本题就是在 LeetCode 78 子集的基础上加了去重的操作（两步： 排序+去重）
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        int index = 0;
        int depth = 0;
        int len = nums.length;
        // 排序
        Arrays.sort(nums);
        dfs(nums, res, path, index, depth, len);
        return res;
    }

    public void dfs(int[] nums, List<List<Integer>> res, Deque<Integer> path, int index, int depth, int len){
        res.add(new ArrayList(path));
        if(len == depth){
            return;
        }

        for(int i = index; i < nums.length; i++){
        	// 去重
            if(i > index && nums[i] == nums[i-1])
                continue;
            path.addLast(nums[i]);
            dfs(nums, res, path, i+1, depth+1, len);
            path.removeLast();
        }
    }
}

LeetCode 78 子集（Java 标准回溯算法 天然无添加）

这篇关于LeetCode 90 子集 II（Java 标准回溯算法 天然无添加）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！