47. Permutations II

Problem:

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example:

Input: [1,1,2]
Output:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

Solution:

Same as 46. Permutations. To avoid duplication, when picking a number for a position, only pick the unused. Either sort the nums or use a set to mark.

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
let permuteUnique = function (nums) {
  const result = [];
  _permuteUnique(nums, 0, result);
  return result;
};

function _permuteUnique(nums, start, result) {
  if (start === nums.length) {
    result.push(nums.slice());
  }

  const used = new Set();
  const begin = nums[start];
  for (let i = start; i < nums.length; i++) {
    const next = nums[i];

    if (used.has(next)) {
      continue;
    }

    used.add(next);

    nums[start] = next;
    nums[i] = begin;

    _permuteUnique(nums, start + 1, result);

    nums[start] = begin;
    nums[i] = next;
  }
}

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆

☆: .｡. o(≧▽≦)o .｡.:☆☆: .｡. o(≧▽≦)o .｡.:☆