回溯

前两题看到面试题中出现了递归回溯，当时心里没想出来，也是一阵苦逼，直接GG。今天回过头来重新复习复习，一下包含两道递归简单和一个回溯中等。时间上同样是对自己做了要求。来，下面开始上题：

斐波那契数列

虽然简单，但是经典啊！现在让大家手写，能手写出来吗？这其中包含的是递归的魅力，题目我就不再赘述了，下面我就直接上码了：

func fib(N int) int {
    if N == 0 {
        return 0
    }
    if N == 1 {
        return 1
    }
    return fib(N-1) + fib(N-2)
}

方法和思想都能简单，注意体会，每个数都是前两个数之和。

爬楼梯

这也是到简单的题目，使用的方法也和上面的题目一样，但是还是不能轻敌哈，题目的意思是，输出N，标识有N级台阶，限制是每次能爬一阶或者两阶，输出爬完N阶能够使用的方法次数。
是不是和斐波那锲很想呢？是的。当时有个思想误区：爬完楼梯的方法，每次爬方法加上下次能爬的方法，例如：爬3阶=先爬2阶+再爬1阶。这是个思想误区，当时从斐波那契回来，就惯性思维了这么想象。正确的是：爬3阶= 第一次爬2阶的方法+第一次还可以只爬一阶的方法。每次有两个选择，使用每次的两个选择递归。下面上码：

func climbStairs(n int) int {
    if n == 0 {
        return 1
    }
    if n < 0 {
        return 0
    }
    var mem = make(map[int]int)
    return climb(n-1, mem) + climb(n-2, mem)
}
func climb(n int, mem map[int]int) int {
    if n == 0 {
        return 1
    }
    if n < 0 {
        return 0
    }
    if r, ok := mem[n]; ok {
        return r
    }
    r := climb(n-1, mem) + climb(n-2, mem)
    mem[n] = r
    return r
}

上面的代码是在做了一次优化之后输出的，因为题目对时间有限制，无脑的递归固然是可以解决问题，但是时间限制过不去，这里使用map记录了每次对应的楼梯的使用方法，避免了重复的递归。主要还是了解其中的递归的作用，认真体会。

全排列

然后这这道中等的全排列题目，题目的意思也很简单，就是输入数组，输出全排列后的二维数组。不错，也是用到的递归，有个小点是去重，这样就OK了。下面上码：

package main

func permute(nums []int) [][]int {
    if len(nums) == 0 {
        return nil
    }
    var r [][]int
    var info = make([]int, 0, len(nums))
    mem := make(map[int]struct{})
    _permute(nums, mem, &r, info)
    return r
}

func _permute(num []int, mem map[int]struct{}, rInfos *[][]int, rInfo []int) {
    if len(rInfo) == len(num) {
        *rInfos = append(*rInfos, append([]int{}, rInfo...))
        return
    }
    for _, v := range num {
        if _, ok := mem[v]; ok {
            continue
        }
        rInfo = append(rInfo, v)
        mem[v] = struct{}{}
        _permute(num, mem, rInfos, rInfo)
        delete(mem, v)
        rInfo = rInfo[:len(rInfo)-1]
    }
}

大致思路就是每次递归都遍历数组，为了避免重复，使用map记录下了每次记录的数子，知道数组长度和输入数组长度一致是给二维数组添加，添加的时候有个小点，append的时候不能直接append当前的以为数组rInfo，应为切片的底层时间还是数组，这样append造成的结果就是二维数组里的结果是都是一个，所以这里重新创建了新切片。然后需要注意的就是每次遍历的时候对map的删除和当前以为数组的弹出。最后就是时间上的问题，做这道题总共花了16分钟，感觉要是面试，有点悬了！

下课！