問題描述：
子集和問題的一個實體為<S,M>，其中S={x1,x2,…,xn}是一個正整數的集合，M是一個正整數，找出S的所有子集S1，使得S1中所有元素的和為M，試設計一個解子集和問題的回溯法，
樣例輸入：
5 10 12 13 15 18
30
樣例輸出：
5 10 15
5 12 13
12 18
樣例說明：
輸入第一行是集合S,第二行是整數M;輸出每一行代表一個解
#include <iostream>
using namespace std;
int s[100],n;
int m;
int flag[100];//標記被使用的元素，便于輸出
int sum=0;//臨時的子集和
void dfs(int t)
{
if(sum==m)
{
for(int i=0;i<n;i++)
{
if(flag[i])
cout<<s[i]<<" ";
}
cout<<endl;
}
else if(sum>m||t>=n)//剪枝函式
return;
else
{
flag[t]=1;
sum+=s[t];
dfs(t+1);
flag[t]=0;
sum-=s[t];
dfs(t+1);
}
}
int main()
{
int x,i=0;
while(cin>>x)
{
s[i++]=x;
if(cin.get()=='\n')
break;
}
n=i;
cin>>m;
dfs(0);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/390579.html
標籤：其他
上一篇：洛谷【4】P1035 [NOIP2002 普及組] 級數求和
下一篇：程式員影響力之路——網羅系統