题目 memorable

leetcode:46

代码与解析

这题卡我挺长时间。
借鉴了carl大佬的思路，尤其文章中的那个图，讲解的很到位，

这里借鉴一下carl大佬博客的一张图（如有冒犯请联系我，立即删除）

这道题和491题不同
491题里面used数组是用来去重的，虽说这道题也是用来去重，他的主要作用是标记在这一个树杈里面用了哪些元素。

排列和组合不一样，排列是有序的，[1,2,3]和[3,2,1]是两个不同的排列， 元素1在[1,2,3]里面已经使用过一次了，但在[3,2,1]里面还要再使用一次，所以就不用使用startIndex了。需要使用used数组来标记一个树杈中已经选择的元素

回溯三部曲：

• 确定参数及返回值
  不需要参数和返回值

• 确定终止条件
  但path数组长度等于给定数组长度时，将path结果转移到res

if len(path)==len(nums){
    tmp := make([]int, len(path))
    copy(tmp, path)
    res = append(res, tmp)
    return 
}

• 确定单层逻辑
  用了两种写法，题解里还有大佬用map，和数组存bool类型的值来解决问题,https://leetcode-cn.com/problems/permutations/solution/hui-su-by-weedge-mqzf/例如链接里的这种。

    //切记这个要复位
    used[nums[i]+10] = 0

因为每个小树杈的情况是不同的，前一个树杈使用过后，后一个还要使用，不清空的话，后一个树杈会以为该元素已经使用了。

for i:=0;i<len(nums); i++{
    if used[nums[i]+10]==1{
        continue
    }

    used[nums[i]+10] = 1
    // fmt.Println(used)
    path = append(path, nums[i])
    backtracking()
    path = path[:len(path)-1]
    // 切记这个要复位
    used[nums[i]+10] = 0
}

或许这种方式更容易理解

for i:=0;i<len(nums); i++{
    if used[i]==1{
        continue
    }

    used[i] = 1
    path = append(path, nums[i])
    backtracking()
    path = path[:len(path)-1]
    used[i] = 0
}

整体代码：

func permute(nums []int) [][]int {
    res := [][]int{}
    path := []int{}
    used := make([]int, 21)
    var backtracking func()
    backtracking = func(){
        if len(path)==len(nums){
            tmp := make([]int, len(path))
            copy(tmp, path)
            res = append(res, tmp)
            return 
        }
        // used = make([]int, 21)
        for i:=0;i<len(nums); i++{
            if used[i]==1{
                continue
            }
            used[i] = 1
            // fmt.Println(used)
            path = append(path, nums[i])
            backtracking()
            path = path[:len(path)-1]
            used[i] = 0
        }
    }
    backtracking()
    return res
}