抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

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)
        }
    }
}

0条评论

发表评论