1_92_golang解法

package __Recursion_DFS

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "strings"
    "testing"
)

func TestAcwing92(t *testing.T) {
    // 使用 bufio 读取输入
    reader := bufio.NewReader(os.Stdin)
    line, _ := reader.ReadString('\n') // 读取一行输入
    line = strings.TrimSpace(line)     // 去掉换行符和空格
    n, err := strconv.Atoi(line)       // 转换为整数
    if err != nil {
        fmt.Println("输入错误，请输入一个整数")
        return
    }

    // 创建 dfsnums 实例并调用 dfs 方法
    dfs := Newdfsnums(n)
    dfs.dfs(1) // 从第 1 个位置开始递归
}

// 定义 dfsnums 结构体
type dfsnums struct {
    n  int   // 数字的个数
    st []int // 状态数组，记录每个数字是否被使用
}

// 构造函数，初始化 dfsnums
func Newdfsnums(n int) *dfsnums {
    return &dfsnums{
        n:  n,
        st: make([]int, n+1), // 状态数组大小为 n+1，方便从 1 开始索引
    }
}

// 深度优先搜索方法
func (d *dfsnums) dfs(x int) {
    // 递归边界：当 x > n 时，输出当前排列
    if x > d.n {
        for i := 1; i <= d.n; i++ {
            if d.st[i] == 1 { // 只输出状态为 1 的数字
                fmt.Print(i, " ")
            }
        }
        fmt.Println() // 换行
        return
    }

    // 选择当前数字
    d.st[x] = 1
    d.dfs(x + 1) // 递归处理下一个数字
    d.st[x] = 0  // 回溯

    // 不选择当前数字
    d.st[x] = 2
    d.dfs(x + 1) // 递归处理下一个数字
    d.st[x] = 0  // 回溯
}