47. Permutations II

Permutations II

Problem Description

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

 

Example 1:

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

Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

Constraints:

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

Approach) Brute Force

let permArr = [];
let usedChars = [];
const permuteUnique = (nums) => {
    permArr = [];
    usedChars = [];
    let data = permute(nums);
    return removeDuplicatesMultiArray(data);
};

const permute = (input) => {
    let ch;
    for (let i = 0; i < input.length; i++) {
        ch = input.splice(i, 1)[0];
        usedChars.push(ch);
        if (input.length == 0) {
            permArr.push(usedChars.slice());
        }
        permute(input);
        input.splice(i, 0, ch);
        usedChars.pop();
    }
    return permArr;
};

const removeDuplicatesMultiArray = (arr) => {
    return arr.map(JSON.stringify).reverse().filter((item, index, arr) => {
        return arr.indexOf(item, index + 1) === -1;
    }).reverse().map(JSON.parse);
};

Approach) Backtrack

var permuteUnique = function(nums) {
    nums.sort();
    const res = [];
  backTracking(res, [], new Set(), nums);

  return res;

  function backTracking(res, tempList, visited = new Set(), nums) {
    if (tempList.length == nums.length) {
      res.push([...tempList]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (visited.has(i)) continue;
      if (i > 0 && nums[i] == nums[i - 1] && !visited.has(i - 1)) continue;
      tempList.push(nums[i]);
      visited.add(i);
      backTracking(res, tempList, visited, nums);
      tempList.pop();
      visited.delete(i);
    }
  }
};

Approach) HashTable (Hash Map)

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
	let resultMap = new Map();
	let theMap = new Map();
	backtrack(nums, resultMap, theMap);

	return [...resultMap.values()];
};

function backtrack(nums, resultMap, map) {
	if (map.size === nums.length) {
	   resultMap.set([...map.values()].join(""), [...map.values()]); 
	   return;
	}
	for (let i = 0; i < nums.length; i++) {
		let available = map.get(i);
		if (available === undefined) {
			map.set(i, nums[i]);
			backtrack(nums, resultMap, map);
			map.delete(i);
		}
	}
}

Approach) Recursion

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permuteUnique = function(nums) {
    const n = nums.length
    let res = []
    nums.sort((x, y) => x - y)
    helper([], new Array(n).fill(false))
    return res
    
    function helper(temp, used) {
        
        if (temp.length === n) {
            res.push(temp.slice())
            return;
        }
        
        for (let i = 0; i < n; i++) {
            if (used[i] || used[i-1] && nums[i] == nums[i-1]) continue;
            
            temp.push(nums[i])
            used[i] = true;
            
            helper(temp, used)
            
            temp.pop()
            used[i] = false;
        }
    }
};

Approach) DFS (Depth First Search)

var permuteUnique = function (nums) {
    const freq = new Map();
    for (let num of nums) {
        if (!freq.has(num)) freq.set(num, 0);
        freq.set(num, freq.get(num) + 1);
    }

    let perm = [];
    let res = [];

    function dfs() {
        if (nums.length === perm.length) {
            res.push([...perm]);
            return;
        }
        for (let key of [...freq.keys()]) {
            if (freq.get(key) > 0) {
                perm.push(key);
                freq.set(key, freq.get(key) - 1);

                dfs();

                perm.pop();
                freq.set(key, freq.get(key) + 1);
            }
        }
    }

    dfs();
    return res;
};

Conclusion

That’s all folks! In this post, we solved LeetCode problem 47. Permutations II

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!