Leetcode 46. 全排列

46. 全排列

解法：回溯

刷了一些题，总算看到labuladong的身影了，这题确实通俗易懂：扒一扒回溯算法的裤子

思路：枚举每个元素，用剩余的元素做决策，元素个数达到给定数组长度时就算一个。

注意：用track.remove(track.lastIndex)和track.removeLast()是两回事，需要用track.removeAt(track.lastIndex)。

时间复杂度：O( n* n! ) 空间复杂度：O( n )

class Solution {

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

    fun permute(nums: IntArray): List<List<Int>> {
        val track = mutableListOf<Int>()
        backstrack(nums, track)
        return res
    }

    private fun backstrack(nums: IntArray, track: MutableList<Int>) {
        if (track.size == nums.size) {
            res.add(track.toMutableList())
            return
        }
        for (i in nums.indices) {
            if (track.contains(nums[i])) continue
            track.add(nums[i])
            backstrack(nums, track)
            track.removeAt(track.lastIndex)
        }
    }
}