46.permutations.md

46. Permutations

private val results = mutableListOf<List<Int>>()

fun permute(nums: IntArray): List<List<Int>> {
    for (i in 0 until nums.size) {
        val used = hashSetOf<Int>()
        used.add(nums[i])
        dfs(nums, mutableListOf(nums[i]), used)
    }
    return results
}

private fun dfs(nums: IntArray, permutation: MutableList<Int>, used: HashSet<Int>) {
    if (permutation.size == nums.size) {
        results.add(ArrayList<Int>(permutation))
        return
    }
    
    for (num in nums) {
        if (used.contains(num)) continue
        used.add(num)
        permutation.add(num)
        dfs(nums, permutation, used)
        permutation.removeAt(permutation.size - 1)
        used.remove(num)
    }
}

• Time Complexity: O(n! * n)
• Space Complexity: O(n).