Permutations_II.js

/*
Permutations II
https://leetcode.com/problems/permutations-ii/

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]
]
*/


var permuteUnique = function(nums) {
  var map = {};
  for(var i = 0; i < nums.length; i++) {
      var value = nums[i];
      map[value] = (map[value]) ? map[value] + 1 : 1;
  }
  
  return permuteUniqueAux(nums.length, map, []);
};

var permuteUniqueAux = function(n, map, currentSol) {
  if(currentSol.length === n) {
    return [currentSol];
  }

  var ret = [];
  for(var num in map) {
    const occ = map[num];
    if(occ === 1) {
      delete map[num];
    } else {
      map[num] = occ -1 ;
    }
    ret = [...ret, ...permuteUniqueAux(n, map, currentSol.concat(num))];
    map[num] = occ;
  }

  return ret;
};

module.exports.permuteUnique = permuteUnique;