Leetcode 46 full arrangement

1. subject

Give an array without duplicate numbers nums , Back to its All possible permutations . You can In any order Return to the answer .

2. Analysis of problem solving ideas

This topic is the full arrangement topic of high school , Let's look at the rules first .

• When the input nums = [1] when , There is only one , So there is only one sort [1].

• When the input nums = [1, 2] when , Two figures , There are two ways to sort ： [2, 1], [1, 2] . There are two new sorts , You can put it first. 1 Fixed , It's up there [1], here , Will be 2 Insert into [1] In this line , There are two ways , Insert index by 0 The location of , namely [2, 1], The other is to insert index by 1 The location of , namely [1, 2]

• When the input nums = [1, 2, 3] when , As described in step 2 , The input of three numbers is the third number 3 Insert into all queues with only two numbers . therefore , The logic is simple , The first queue of two numbers is [2, 1], therefore 3 You can insert this pair of columns 0, 1, 2 Three places , Get... Separately [3, 2, 1], [2, 3, 1],[2, 1 , 3]. Similarly, we can get another three queues

According to this idea, it is easy to write the code .

3. Code implementation

Used here kotlin , The code is as follows ：

fun permute(nums: IntArray): List<List<Int>> {
    
    var result = ArrayList<List<Int>>()
    for (item in nums) {
    
        var tempResult = ArrayList<List<Int>>()
        if (result.size <= 0) {
    
            tempResult.add(listOf(item))
        } else {
    
            result.forEach {
     listItem ->
                for (it in 0..listItem.size) {
    
                    var newList = ArrayList<Int>()
                    newList.addAll(listItem)
                    newList.add(it, item)
                    tempResult.add(newList)
                }
            }
        }
        result = tempResult
    }
    return result
}