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
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
}