code.ashish.me

Atom feed

Recently added: 02 Count Of Subset Sum, 416 Partition Equal Subset Sum, 01 Subset Sum, 518 Coin Change 2, 983 Minimum Cost For Tickets

06 Permutations 2

/**
 *
 * Ashish Patel
 * e: ashishsushilPatel@gmail.com
 * w: https://ashish.me
 *
 */

const permutations2 = nums => {
  const result = []
  const visited = new Set()
  nums.sort()
  const backtrack = curr => {
    if (nums.length == curr.length) {
      result.push([...curr])
    } else {
      for (let i = 0; i < nums.length; i++) {
        if (visited.has(i) || (i > 0 && nums[i] === nums[i - 1] && !visited.has(i - 1))) {
          continue
        }
        visited.add(i)
        curr.push(nums[i])
        backtrack(curr)
        visited.delete(i)
        curr.pop()
      }
    }
  }
  backtrack([])
  return result
}

console.log(permutations2([1, 1, 2]))

Created 2022-02-25T20:02:36+00:00 · Edit