解題程式碼

var subsetsWithDup = function (nums) {
  const result = [[]];
  const subsetsSet = new Set();
  nums = nums.sort((a, b) => a - b);

  const backtracking = (subsets) => {
    if (subsetsSet.has(subsets.join('-')) || subsets.length === 0) return;

    result.push(subsets);
    subsetsSet.add(subsets.join('-'));
    for (let i = 0; i < subsets.length; i++) {
      backtracking([...subsets.slice(0, i), ...subsets.slice(i + 1)]);
    }
  };

  backtracking(nums);

  return result;
};

var subsetsWithDup = function (nums) {
  const result = [];
  nums.sort((a, b) => a - b);

  const backtracking = (index, subSet) => {
    result.push([...subSet]);

    for (let i = index; i < nums.length; i++) {
      if (i > index && nums[i] === nums[i - 1]) {
        continue;
      }

      subSet.push(nums[i]);
      backtracking(i + 1, subSet);
      subSet.pop();
    }
  };

  backtracking(0, []);

  return result;
};

解題思路、演算法

從 78 題再加點變化的題目，這題的 input nums 會包含重複的元素，所以像 [4,4,4,1,4] 這種就要先做排序，

才不會把重複的 subsets 加到最終結果中。

解法的時間、空間複雜度

時間複雜度: O(n * 2^n) + O(n * log n)，n 是 nums 的長度，因為每個數字都有可取可不取，放入子集的情況，所以 2^n
空間複雜度: O(n * 2^n)，考慮子集的個數和長度

參考資料

Subsets II - Backtracking - Leetcode 90 - Python

「代码随想录」带你学透回溯算法！90. 子集 II:【彻底理解子集问题如何去重】

详解组合问题回溯的“同层去重”操作