go - 递归期间缺少排列

Question

我在 go playground 中有一个示例递归代码，有 2 个“？”，目标是生成所有二进制字符串替换 ?使用 0 或 1，它应该显示 4 个结果，但只显示 3 个。即缺少 1100101

package main

import (
    "fmt"
    //"strings"
    //"strconv"
)

func main() {
    str := "1?0?101"
    mstr := []byte(str)
    q := []byte("?")[0]
    a := []byte("0")[0]
    b := []byte("1")[0]
    fmt.Println(mstr)
    allstr(mstr, 0, len(mstr), q, a, b)

}

func allstr(mstr []byte, index int, size int, q, a, b byte) {

    if index >= size {
        fmt.Println(string(mstr))
        return
    }
    if mstr[index] == q {
        mstr[index] = a
        allstr(mstr, index+1, size, q, a, b)

        mstr[index] = b
        allstr(mstr, index+1, size, q, a, b)

    } else {

        allstr(mstr, index+1, size, q, a, b)
    }

}

去 Playground :https://play.golang.org/p/4e5NIOS9fG4

输出:

[49 63 48 63 49 48 49]
1000101
1001101
1101101

Answer 1

您需要在递归回溯期间撤消对主 byte slice 的写入:

if mstr[index] == q {
        mstr[index] = a
        allstr(mstr, index+1, size, q, a, b)

        mstr[index] = b
        allstr(mstr, index+1, size, q, a, b)

        mstr[index] = q         // <--- add this
} 

https://play.golang.org/p/-JEsVGFcsQo