(24)Go递归求组合类问题

问题1：求电话号码的字母组合 //

这是一个树类问题，可借组树天然的递归性质求解，结构如下图：

// 字符串查询表
var m []string = []string{
    "abc",
    "def",
    "ghi",
    "jkl",
    "mno",
    "pqrs",
    "tuv",
    "wxyz",
}

// 时间复杂度为3^n=O(2^n)
func letterCombinations(digits string) []string {
    length := len(digits)
    if length == 0 {
        return nil
    }
    res := []string{}
    combination(digits, length-1, 0, &res, "")

    return res
}

// 深度优先遍历方式,从上而下添加字符方式
func combination(digits string, endI int, index int, res *[]string, str string) {
    // 递归终止条件
    if index == endI {
        // 每次遍历到底部,在底部把str加到res里面
        for _, v := range m[digits[index]-'2'] {
            *res = append(*res, str+string(v))
        }
    } else {
        // 递归过程
        for _, v := range m[digits[index]-'2'] {
            // 每次遍历到底部,在底部把str加到res里面
            combination(digits, endI, index+1, res, str+string(v))
        }
    }
}

提交leetcode，通过

问题2：求全排列 //

一样是树问题，树的结构如下图示：

递归结构:perms(nums[0...n-1]) = {取出1个数字} + perms(nums[{0...n-1} - 这个数字])

func permute(nums []int) [][]int {
    n := len(nums)
    if n == 0 {
        return nil
    }

    res := [][]int{}           //组合集合
    arr := make([]int, n)      //组合
    visited := make([]bool, n) //是否已经访问过
    flashBack(nums, 0, n, visited, arr, &res)
    return res
}

// 深度优先遍历方式,自上而下添加元素
// 向arr[0...index-1]末尾添加第index位元素,获得arr[0...index]元素的组合
func flashBack(nums []int, index, n int, visited []bool, arr []int, res *[][]int) {

    // 递归终止条件
    if index == n {
        // 因为arr加在res里面后,arr修改,res里面也会被修改
        // 所以这里做1次复制
        buf := append([]int{}, arr...)
        *res = append(*res, buf)
    } else {

        // 递归过程
        for i := 0; i < n; i++ {
            if !visited[i] {
                visited[i] = true
                // 推进元素,用完不同推出元素,下次循环重新覆盖
                arr[index] = nums[i]
                flashBack(nums, index+1, n, visited, arr, res)
                // 用完重置为false,下次循环得用
                visited[i] = false
            }
        }
    }
}

提交leetcode，通过

问题3：求全排列2，和问题2对比 //

由上图可以看出，每次取出元素i后，只需从i之后的区间寻找下一个可填充的元素，即在[i+1,n]区间里寻找

方法1：未优化版本，理解未优化版本有助于理解优化版本
func combine(n int, k int) [][]int {
    if n <= 0 || k > n || k <= 0 {
        return nil
    }

    res := [][]int{}      //组合集合
    arr := make([]int, k) //长度k的组合
    generateCombinations(n, k, 0, 1, arr, &res)
    return res
}

// index: arr[index]位元素赋值
// start: 从[start...n]开始寻找下一个可以填充的元素
// 函数功能：从[start...n]里寻找下一位可以填充的元素,填充在arr[index]位置
func generateCombinations(n, k, index, start int, arr []int, res *[][]int) {

    // 递归终止条件
    if index == k {
        // 做一次复制
        buf := append([]int{}, arr...)
        *res = append(*res, buf)
    } else {
        // 递归过程
        for i := start; i <= n; i++ {
            arr[index] = i
            generateCombinations(n, k, index+1, i+1, arr, res)
        }
    }
}

方法1提交leetcode，通过

优化：arr[0...index-1]的元素已经填充，剩下k-index个空位，
因此[start...n]至少要有k-index个元素
即 k-index<=n-start+1，推导出 start<=n+1-(k-index)

// 优化1
func generateCombinations2(n, k, index, start int, arr []int, res *[][]int) {

    // 递归终止条件
    if index == k {
        // 做一次复制
        buf := append([]int{}, arr...)
        *res = append(*res, buf)
    } else {
        // 优化：arr[0...index-1]的元素已经填充，剩下k-index个空位，
        // 因此[start...n]至少要有k-index个元素
        // 即 k-index<=n-start+1，推导出 start<=n+1-(k-index)

        // 递归过程
        for i := start; i <= n+1-(k-index); i++ {
            arr[index] = i
            generateCombinations2(n, k, index+1, i+1, arr, res)
        }
    }
}

在优化1的基础上进一步优化：每次arr加1个元素，令k-1，即剩下k-1个位置，
递归终止条件变成k==0
func generateCombinations3(n, k, index, start int, arr []int, res *[][]int) {
    if k == 0 {
        buf := append([]int{}, arr...)
        *res = append(*res, buf)
    } else {
        // 每次arr加1个元素,k-1,即剩下k-1个空位置
        for i := start; i <= n+1-k; i++ {
            arr[index] = i
            generateCombinations3(n, k-1, index+1, i+1, arr, res)
        }
    }
}

方法3提交leetcode，通过

有bug欢迎指出