90. Subsets II

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @return {number[][]}
 */

题目给我们一个包含重复元素的数字数组 nums

要求我们返回 nums 的所有不重复子集组合

解题思路

需要求组合，优先想到回溯法

这题的难点在于要如何在数组包含重复元素的情况下，使子集不重复

这就需要用到回溯法的剪枝操作了

当我们在回溯中遍历 nums 时，我们可以加入如下判断：

if (i > cur && nums[i] === nums[i - 1])

这个剪枝可以让我们忽略掉重复的元素

Javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsetsWithDup = function (nums) {
    const res = []
    nums.sort((a, b) => a - b)
    const len = nums.length

    const backtrack = (cur, arr) => {
        res.push([...arr])

        for (let i = cur; i < len; i++) {
              // key pruning
            if (i > cur && nums[i] === nums[i - 1]) {
                continue
            }
            arr.push(nums[i])
            backtrack(i + 1, arr)
            arr.pop()
        }
    }

    backtrack(0, [])
    return res
};

复杂度分析

时间

排序：O(nlogn)

回溯：O(2^n)

数组复制：O(n)

总体：

空间

回溯：O(n)

Res 数组： 数组最多有 个元素，每个元素都是数组，平均长度是 n/2 个元素