本文共 686 字，大约阅读时间需要 2 分钟。

问题描述：给定集合S，S中有n个正整数，M是一个正整数。子集和问题判定是否存在S的一个子集S1，使得S1中各元素之和等于M。请设计回溯法求解子集和问题，如果问题无解，输出“No Solution”,问题有解，则输出满足子集S1中各元素的值。

#include 
   
    using namespace std;const int N = 10005;int a[N], n, m, rec[N]; bool nu;void dfs(int start, int sum, int cnt) {
   	if (sum > m) return ;//剪枝 	if (sum ==m) {
   		for (int i = 0; i < cnt; i++) 		   cout<
    
     <<" ";		nu= true;//记录是否找到一组解 		return ;	}	for (int i = start; i <= n; i++) {
    //重复性剪枝 		rec[cnt] = a[i];  //记录当前选的值 		dfs(i + 1, sum + a[i], cnt + 1); //对下一个进行搜索 		if (nu) 			return;	}}int main() {
   	cin>>n>>m;	for (int i = 1; i <= n; i++) {
   		cin>>a[i];	}	dfs(1, 0, 0);	if (!nu) 	cout<<"Solution"<
    
   

转载地址：http://tyezi.baihongyu.com/