四次抽签!

2023-12-24 20:42:57

from book:挑战程序设计竞赛

编辑工具:vscode

编辑语言:Go

思路:使用DFS(四层for循环低效且容易超时)

code:

package main

import "fmt"

func main() {
	n := 3 //len(k)
	m := 10
	k := []int{1, 3, 5}
	fmt.Print(solve(n, m, k))

}

func solve(n int, m int, k []int) bool {
	dfs(k, 0, 0, m)
	return check
}

var check = false

func dfs(k []int, cur int, sum int, target int) {
	if cur == 4 { //始终是 取4次
		fmt.Println(cur, sum)
		if sum == target {
			check = true
		}
		return
	}
	for i := 0; i < len(k); i++ {
		if !check { //剪枝 已得到结果故直接退出
			dfs(k, cur+1, sum+k[i], target)
		} else {
			return
		}
	}
}

?

文章来源:https://blog.csdn.net/qq_60678811/article/details/135175890
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。