算法题/排列组合：含重复数字的子集

题目

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

示例1：

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

示例2：

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

解答

Java

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;
        }
        tempSubset.add(nums[i]);
        hasVisited[i] = true;
        backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
        hasVisited[i] = false;
        tempSubset.remove(tempSubset.size() - 1);
    }
}

JavaScript

function subsetsWithDup(nums) {
    nums.sort((a, b) => a - b);
    const subsets = [];
    const tempSubset = [];
    const hasVisited = new Array(nums.length).fill(false);
    for (let size = 0; size <= nums.length; size++) {
        backtracking(0, tempSubset, subsets, hasVisited, size, nums);
    }
    return subsets;
}

function backtracking(start, tempSubset, subsets, hasVisited, size, nums) {
    if (tempSubset.length === size) {
        subsets.push([...tempSubset]);
        return;
    }
    for (let i = start; i < nums.length; i++) {
        if (i !== 0 && nums[i] === nums[i - 1] && !hasVisited[i - 1]) {
            continue;
        }
        tempSubset.push(nums[i]);
        hasVisited[i] = true;
        backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums);
        hasVisited[i] = false;
        tempSubset.pop();
    }
}

Python

def subsetsWithDup(nums):
    nums.sort()
    subsets = []
    tempSubset = []
    hasVisited = [False] * len(nums)
    for size in range(len(nums) + 1):
        backtracking(0, tempSubset, subsets, hasVisited, size, nums)
    return subsets


def backtracking(start, tempSubset, subsets, hasVisited, size, nums):
    if len(tempSubset) == size:
        subsets.append(list(tempSubset))
        return
    for i in range(start, len(nums)):
        if i != 0 and nums[i] == nums[i - 1] and not hasVisited[i - 1]:
            continue
        tempSubset.append(nums[i])
        hasVisited[i] = True
        backtracking(i + 1, tempSubset, subsets, hasVisited, size, nums)
        hasVisited[i] = False
        tempSubset.pop()

Go

func subsetsWithDup(nums []int) [][]int {
	sort.Ints(nums)
	subsets := [][]int{}
	tempSubset := []int{}
	hasVisited := make([]bool, len(nums))
	for size := 0; size <= len(nums); size++ {
		backtracking(0, tempSubset, &subsets, hasVisited, size, nums)
	}
	return subsets
}

func backtracking(start int, tempSubset []int, subsets *[][]int, hasVisited []bool, size int, nums []int) {
	if len(tempSubset) == size {
		tmp := make([]int, len(tempSubset))
		copy(tmp, tempSubset)
		*subsets = append(*subsets, tmp)
		return
	}
	for i := start; i < len(nums); i++ {
		if i != 0 && nums[i] == nums[i-1] && !hasVisited[i-1] {
			continue
		}
		tempSubset = append(tempSubset, nums[i])
		hasVisited[i] = true
		backtracking(i+1, tempSubset, subsets, hasVisited, size, nums)
		hasVisited[i] = false
		tempSubset = tempSubset[:len(tempSubset)-1]
	}
}