47.全排列II

链接：47.全排列II
难度：Medium
标签：数组、回溯
简介：给定一个可包含重复数字的序列，返回所有不重复的全排列。

题解 1 - typescript

• 编辑时间：2020-09-18
• 执行用时：588ms
• 内存消耗：48.9MB
• 编程语言：typescript
• 解法介绍：递归后利用 set 去重。

function permuteUnique(nums: number[]): number[][] {
  const len = nums.length;
  if (len === 1) return [nums];
  const res: number[][] = [];
  for (let i = 0; i < len; i++) {
    res.push(
      ...permuteUnique([...nums.slice(0, i), ...nums.slice(i + 1)]).map(v => [nums[i], ...v])
    );
  }
  // 去重
  const set = new Set(res.map(v => v.join(':')));
  const ans: number[][] = [];
  for (const arr of set) {
    ans.push(arr.split(':').map(v => parseInt(v)));
  }
  return ans;
}

题解 2 - typescript

• 编辑时间：2021-08-14
• 执行用时：176ms
• 内存消耗：44.5MB
• 编程语言：typescript
• 解法介绍：set 去重。

function permuteUnique(nums: number[]): number[][] {
  const ans = new Set<string>();
  add(nums);
  return [...ans].map(v => v.split('::').map(v => +v));
  function add(list: number[], q: number[] = []): void {
    if (list.length === 1) {
      q.push(list[0]);
      ans.add(q.join('::'));
      q.pop();
      return;
    }
    for (let i = 0; i < list.length; i++) {
      q.push(list[i]);
      add([...list.slice(0, i), ...list.slice(i + 1)], q);
      q.pop();
    }
  }
}