// https://leetcode.com/problems/permutations
fun permute(nums: IntArray): List<List<Int>> {
    return mutableListOf<List<Int>>().also {
        buildPermutations(
            nums = nums,
            usedNums = BooleanArray(nums.size),
            permutation = mutableListOf(),
            permutations = it
        )
    }
}

private fun buildPermutations(
    nums: IntArray,
    usedNums: BooleanArray,
    permutation: MutableList<Int>,
    permutations: MutableList<List<Int>>
) {
    if (permutation.size == nums.size) {
        permutations.add(permutation.toList())
        return
    }
    for ((index, num) in nums.withIndex()) {
        if (usedNums[index]) continue
        usedNums[index] = true
        permutation.add(num)
        buildPermutations(nums = nums, usedNums = usedNums, permutation = permutation, permutations = permutations)
        permutation.remove(num)
        usedNums[index] = false
    }
}

// https://leetcode.com/problems/permutations
fun permute(nums: IntArray): List<List<Int>> {
    return mutableListOf<List<Int>>().also {
        buildPermutations(
            nums = nums,
            usedNums = BooleanArray(nums.size),
            permutation = mutableListOf(),
            permutations = it
        )
    }
}

private fun buildPermutations(
    nums: IntArray,
    usedNums: BooleanArray,
    permutation: MutableList<Int>,
    permutations: MutableList<List<Int>>
) {
    if (permutation.size == nums.size) {
        permutations.add(permutation.toList())
        return
    }
    for ((index, num) in nums.withIndex()) {
        if (usedNums[index]) continue
        usedNums[index] = true
        permutation.add(num)
        buildPermutations(nums = nums, usedNums = usedNums, permutation = permutation, permutations = permutations)
        permutation.remove(num)
        usedNums[index] = false
    }
}
