90.子集2.md

90. 子集 II

url

题目

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

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

方法

code

js

let subsetsWithDup = nums => {
    let res = []
    let marked = Array(nums.length).fill(false)
    let dfs = (start, size, list) => {
        if (list.length === size) {
            res.push(list.slice())
            return
        }
        for (let i = start; i < nums.length; i++) {
            if (i !== 0 && nums[i] === nums[i-1] && !marked[i-1])
                continue
            if (marked[i])
                continue
            list.push(nums[i])
            marked[i] = true
            dfs(i, size, list)
            marked[i] = false
            list.pop()
        }
    }
    nums.sort((a, b) => (a - b))
    for (let size = 0; size <= nums.length; size++) {
        dfs(0, size, [])
    }
    return res
}

go

func subsetsWithDup(nums []int) [][]int {
	var res [][]int
	marked := make([]bool, len(nums))
	var dfs func(nums []int, start, size int, list []int)
	dfs = func(nums []int, start, size int, list []int) {
		if len(list) == size {
			res = append(res, append([]int{}, list...))
			return
		}
		for i := start; i < len(nums); i++ {
			if i != 0 && nums[i] == nums[i-1] && !marked[i-1] {
				continue
			}
			if marked[i] {
				continue
			}
			list = append(list, nums[i])
			marked[i] = true
			dfs(nums, i, size, list)
			marked[i] = false
			list = list[:len(list)-1]
		}
	}
	sort.Ints(nums)
	for size := 0; size <= len(nums); size++ {
		dfs(nums, 0, size, []int{})
	}
	return res
}

java

class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> subsets = new ArrayList<>();
        List<Integer> tempSubset = new ArrayList<>();
        boolean[] hasVisited = new boolean[nums.length];
        for (int size = 0; size <= nums.length; size++) {
            backtracking(0, tempSubset, subsets, hasVisited, size, nums); // 不同的子集大小
        }
        return subsets;
    }
    private void backtracking(int start, List<Integer> tempSubset, List<List<Integer>> subsets, boolean[] hasVisited,
                            final int size, final int[] nums) {

        if (tempSubset.size() == size) {
            subsets.add(new ArrayList<>(tempSubset));
            return;
        }
        for (int i = start; i < nums.length; i++) {
            if (i != 0 && nums[i] == nums[i - 1] && !hasVisited[i - 1]) {
                continue;
            }
            if (hasVisited[i])
                continue;
            tempSubset.add(nums[i]);
            hasVisited[i] = true;
            backtracking(i, tempSubset, subsets, hasVisited, size, nums);
            hasVisited[i] = false;
            tempSubset.remove(tempSubset.size() - 1);
        }
    }

}