子集 II

题目

给定一个可能包含重复元素的整数数组 nums, 返回该数组所有可能的子集.

说明: 解集不能包含重复的子集.

提示:

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

示例

输入: [1, 2, 2]

输出: [ [], [ 1 ], [ 1, 2 ], [ 1, 2, 2 ], [ 2 ], [ 2, 2 ] ]

题解

本题是 78. 组合总数 的一个变种, 核心思想看这篇文章即可, 只不过本题加入了可能包含重复元素的情况, 直接套用 visited 大法即可.

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
  const n = nums.length
  const res = []
  const visited = new Array(n).fill(false)
  nums.sort((a, b) => a - b)

  const dfs = (begin, track) => {
    res.push(track.slice())

    for (let i = begin; i < n; i++) {
      if (nums[i - 1] === nums[i] && i - 1 >= 0 && !visited[i - 1]) continue
      if (visited[i]) continue

      track.push(nums[i])
      visited[i] = true
      dfs(i + 1, track)
      track.pop()
      visited[i] = false
    }
  }

  dfs(0, [])

  return res
}

Rust

pub fn subsets_with_dup(nums: Vec<i32>) -> Vec<Vec<i32>> {
    let mut res = Vec::new();
    let mut visited = vec![false; nums.len()];

    let mut nums = nums;
    nums.sort();

    dfs(0, &nums, &mut visited, &mut vec![], &mut res);

    res
}

fn dfs(
    begin: usize,
    nums: &Vec<i32>,
    visited: &mut Vec<bool>,
    track: &mut Vec<i32>,
    res: &mut Vec<Vec<i32>>,
) {
    res.push(track.to_vec());

    for i in begin..nums.len() {
        if i >= 1 && nums[i - 1] == nums[i] && !visited[i - 1] {
            continue;
        }

        if visited[i] {
            continue;
        }

        track.push(nums[i]);
        visited[i] = true;
        dfs(i + 1, nums, visited, track, res);
        track.pop();
        visited[i] = false;
    }
}