Java教程

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 标准回溯算法 天然无添加)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!