递归期间缺少排列

Question

I have go a sample recursive code in go playground, there are 2 "?", the target is to generate all binary strings replacing ? with 0 or 1 , it supposes to display 4 results, but only display 3. ie missing 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)
    }

}

Go playground: https://play.golang.org/p/4e5NIOS9fG4

Output:

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

Answer 1

You need to undo the writes to the master byte-slice during recursive-backtracking:

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