[90] 子集 II

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

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

示例 1：

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

输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

示例 2：

输入：nums = [0]

输出：[[],[0]]

这题相比 [78] 子集 来说，增加了包含重复元素的可能，那么这就要求我们对重复元素的路径只取一次。

自然先要排序，将重复元素划分在一起。

由于进行过排序，因此在遍历时，除去第一个值一定会被执行外，若当前节点值与前一个节点相等，则可以判定直接跳过，进行剪枝。

function subsetsWithDup(nums: number[]): number[][] {
  // 先排序
  nums.sort((a, b) => a - b);

  const res: number[][] = [];
  backtrack([], 0);
  return res;

  function backtrack(path: number[], start: number) {
    res.push([...path]);

    for (let i = start; i < nums.length; i++) {
      // 如果遇到值相同的情况，只递归第一个值，其余跳过
      if (i > start && nums[i] === nums[i - 1]) {
        continue;
      }
      // 选择该节点
      path.push(nums[i]);
      // 回溯
      backtrack(path, i + 1);
      // 撤销选择
      path.pop();
    }
  }
}