46. Permutations

题目

Given a collection of distinct integers, return all possible permutations. ###　题意求数组的全部排列

例子

Input: [1,2,3]
Output: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

题解

求排序，和求组合类似，固定住前一位，然后使用use数组标记已在res数组中的元素，再遍历取没标记的元素加进res数组，然后递归取下一个元素，res达到目标个数后输出并返回。返回后把原来加进res数组中的元素移除，在取一下。重复直到结束。

代码

var out [][]int
var use []bool
func permute(nums []int) [][]int {
    Len := len(nums)
    if Len== 0 {
        return nil
    }
    
    out = make([][]int,0)
    use = make([]bool,Len)
    res := make([]int,0)
    Permutatins(nums,Len,res)
    return out
}

func Permutatins(nums []int,n int,res []int){
    if len(res)==n{
        out = append(out,append(make([]int,0),res...))
        return
    }
    
    for i:=0;i<n;i++{
        if use[i]{
            continue
        }
        
        use[i]=true
        res = append(res,nums[i])
        Permutatins(nums,n,res)
        res = res[0:len(res)-1]
        use[i]=false
    }
}

总结

之前就总结果了求组合和排列的算法，所以就不多总结了。可看第78题总结。