9.9全排列Permutations - WisperDin/blog GitHub Wiki

描述

Given a collection of numbers, return all possible permutations.

For example, [1,2,3] have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

思路

参考： https://segmentfault.com/a/1190000003765975#articleHeader9

保证每次从数组中选取一个未选取过的数加入该次搜索的结果中

• 交换法，规定数字两两交换只能跟自己后面的交换
• DFS，每轮搜索加入一个数，维护一个bool数组用于记录每轮搜索时数字是否被选取过

实现

func permute(nums []int) [][]int {
    if len(nums)<=0 {
        return [][]int{}
    }
    if len(nums)==1 {
        return [][]int{{nums[0]}}
    }
    ans := [][]int{}
    //calc(nums,0,&ans)
    tmp := make([]int,len(nums))
    used := make([]bool,len(nums))
    calcDFS(nums,0,tmp,used,&ans)
    return ans
}

func calc(nums []int, pos int, ans *[][]int)  {
    if pos == len(nums) - 1 {
        newNums := make([]int,len(nums))
        for i:=0 ; i < len(nums) ; i ++ {
            newNums[i] = nums[i]
        }
        *ans = append(*ans,newNums)
        return
    }
    
    for i:=pos ; i < len(nums) ; i++ {
        //swap
        nums[i], nums[pos] = nums[pos], nums[i]
        calc(nums,pos+1,ans)
        //reset
        nums[i], nums[pos] = nums[pos], nums[i]
    }
    return
}

func calcDFS(nums []int, pos int, tmp []int, used []bool,  ans *[][]int)  {
    if pos == len(nums) {
        newNums := make([]int,len(tmp))
        for i:=0 ; i < len(nums) ; i ++ {
            newNums[i] = tmp[i]
        }
        *ans = append(*ans,newNums)
        return
    }
    
    for i:=0 ; i < len(nums) ; i++ {
        if used[i] {
            continue
        }
        
        used[i] = true
        tmp[pos] = nums[i]
        calcDFS(nums,pos+1,tmp,used,ans)
        used[i] = false

    }
    return
}