leetcode - [90] Subsets II

2020/06/18

题目描述

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

给一个可能包含重复元素的数组,计算出所有可能的子集。

举个例子:

类似题目:

[78] Subsets

Update at 2020_0907

首先,需要对原始数组进行排序,防止重复添加。

然后,重点在于处理数组中元素的元素,若当前索引i大于原始索引u

并且当前元素nums[i]与前一个元素nums[i - 1]相等,则跳过第i个元素。

来看下示意图:

再来看下实现:

class Solution {

    List<List<Integer>> ans = new LinkedList<>();

    private void dfs(int[] nums, LinkedList<Integer> child, int u){
        ans.add(new LinkedList<>(child));

        for (int i = u; i < nums.length; i++){
            if (i > u && nums[i] == nums[i - 1]) continue;
            child.add(nums[i]);
            dfs(nums, child, i + 1);
            child.removeLast();
        }
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(nums, new LinkedList<>(), 0);
        return ans;
    }
}

解法1

Thanks @issac3

来看下示意图:

关键点在于如何防止重复的集合添加到结果列表中?

注意喔,不是重复的元素。

有两个条件:

第一: 当前位置的索引在递归方法传入的初始索引之后。

第二, 当前元素与前一个元素相等。

if (i > cur && nums[i] == nums[i - 1]){
    continue;
}

还需要格外注意一点:

原始数组一定要升序排列,防止添加重复集合。

来看下实现:

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        
        List<List<Integer>> ans = new LinkedList<>();
        Arrays.sort(nums);
        bt(nums, 0, ans, new LinkedList<>());
        return ans;
    }
    
    private void bt(int[] nums, int cur, List<List<Integer>> ans, LinkedList<Integer> child){
        
        ans.add(new LinkedList<>(child));
        
        for (int i = cur; i < nums.length; i++){
            // Skip duplicates.
            if (i > cur && nums[i] == nums[i - 1]){
                continue;
            }
            child.add(nums[i]);
            bt(nums, i + 1, ans, child);
            child.removeLast();
        }
    }
}


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory