前兩題看到面試題中出現(xiàn)了遞歸回溯，當時心里沒想出來，也是一陣苦逼，直接GG。今天回過頭來重新復習復習，一下包含兩道遞歸簡單和一個回溯中等。時間上同樣是對自己做了要求。來，下面開始上題：

斐波那契數(shù)列

雖然簡單，但是經典??！現(xiàn)在讓大家手寫，能手寫出來嗎？這其中包含的是遞歸的魅力，題目我就不再贅述了，下面我就直接上碼了：

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

方法和思想都能簡單，注意體會，每個數(shù)都是前兩個數(shù)之和。

爬樓梯

這也是到簡單的題目，使用的方法也和上面的題目一樣，但是還是不能輕敵哈，題目的意思是，輸出N，標識有N級臺階，限制是每次能爬一階或者兩階，輸出爬完N階能夠使用的方法次數(shù)。
是不是和斐波那鍥很想呢？是的。當時有個思想誤區(qū)：爬完樓梯的方法，每次爬方法加上下次能爬的方法，例如：爬3階=先爬2階+再爬1階。這是個思想誤區(qū)，當時從斐波那契回來，就慣性思維了這么想象。正確的是：爬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
}

上面的代碼是在做了一次優(yōu)化之后輸出的，因為題目對時間有限制，無腦的遞歸固然是可以解決問題，但是時間限制過不去，這里使用map記錄了每次對應的樓梯的使用方法，避免了重復的遞歸。主要還是了解其中的遞歸的作用，認真體會。

全排列

然后這這道中等的全排列題目，題目的意思也很簡單，就是輸入數(shù)組，輸出全排列后的二維數(shù)組。不錯，也是用到的遞歸，有個小點是去重，這樣就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]
    }
}

大致思路就是每次遞歸都遍歷數(shù)組，為了避免重復，使用map記錄下了每次記錄的數(shù)子，知道數(shù)組長度和輸入數(shù)組長度一致是給二維數(shù)組添加，添加的時候有個小點，append的時候不能直接append當前的以為數(shù)組rInfo，應為切片的底層時間還是數(shù)組，這樣append造成的結果就是二維數(shù)組里的結果是都是一個，所以這里重新創(chuàng)建了新切片。然后需要注意的就是每次遍歷的時候對map的刪除和當前以為數(shù)組的彈出。最后就是時間上的問題，做這道題總共花了16分鐘，感覺要是面試，有點懸了！

下課！