剪枝

递归与回溯

说明

提前跳过不可能达到目标的搜索分支；下例在正整数集合中按剩余和剪枝。

分析

搜索一个正整数子集时，当前和一旦超过目标，就无需再选择后续正数。这个判断依赖所有元素非负；若含负数，超过目标后仍可能被抵消，剪枝就会错误。

图解推演

补充例子：候选 [2,4,7]、目标 6。已选 2、4 时命中；已选 2、7 时总和 9，非负的后续数无法把它降回 6，才能剪掉。若允许 −3，9 仍可能回到 6，原剪枝条件就失效。剪枝优化的是搜索规模，不改变合法解集合。

查看图表代码

适用前提与边界

有效剪枝必须建立在可证明的上下界上。

示例输入与调用

fmt.Println(HasSubsetSum([]int{3, 5, 8}, 11))

运行输出

true

完整 Go 示例

package main

import "fmt"

func HasSubsetSum(a []int, target int) bool {
	var dfs func(int, int) bool
	dfs = func(i, sum int) bool {
		if sum == target {
			return true
		}
		if i == len(a) || sum > target {
			return false
		}
		return dfs(i+1, sum+a[i]) || dfs(i+1, sum)
	}
	return dfs(0, 0)
}

func main() {
	fmt.Println(HasSubsetSum([]int{3, 5, 8}, 11))
}