// https://leetcode.com/problems/permutations-ii
fun permuteUnique(nums: IntArray): List<List<Int>> {
    nums.sort()
    return mutableListOf<List<Int>>().also {
        buildPermutations(nums, 0, it)
    }
}

private fun buildPermutations(nums: IntArray, startIndex: Int, permutations: MutableList<List<Int>>) {
    if (startIndex == nums.lastIndex) {
        permutations.add(nums.toList())
        return
    }
    val swapped = mutableSetOf<Int>()
    var index = startIndex
    while (index <= nums.lastIndex) {
        swapped.add(nums[index])
        nums.swap(startIndex, index)
        buildPermutations(nums = nums, startIndex = startIndex + 1, permutations = permutations)
        nums.swap(startIndex, index)
        index++
        while (nums.getOrNull(index) == nums[startIndex] || swapped.contains(nums.getOrNull(index))) index++
    }
}

private fun IntArray.swap(i: Int, j: Int) {
    if (i == j) return
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}

// https://leetcode.com/problems/permutations-ii
fun permuteUnique(nums: IntArray): List<List<Int>> {
    nums.sort()
    return mutableListOf<List<Int>>().also {
        buildPermutations(nums, 0, it)
    }
}

private fun buildPermutations(nums: IntArray, startIndex: Int, permutations: MutableList<List<Int>>) {
    if (startIndex == nums.lastIndex) {
        permutations.add(nums.toList())
        return
    }
    val swapped = mutableSetOf<Int>()
    var index = startIndex
    while (index <= nums.lastIndex) {
        swapped.add(nums[index])
        nums.swap(startIndex, index)
        buildPermutations(nums = nums, startIndex = startIndex + 1, permutations = permutations)
        nums.swap(startIndex, index)
        index++
        while (nums.getOrNull(index) == nums[startIndex] || swapped.contains(nums.getOrNull(index))) index++
    }
}

private fun IntArray.swap(i: Int, j: Int) {
    if (i == j) return
    val temp = this[i]
    this[i] = this[j]
    this[j] = temp
}
