問題描述

　　從一個大小為n的整數集中選取一些元素，使得它們的和等于給定的值T。每個元素限選一次，不能一個都不選。

輸入格式

　　第一行一個正整數n，表示整數集內元素的個數。
　　第二行n個整數，用空格隔開。
　　第三行一個整數T，表示要達到的和。

輸出格式

　　輸出有若干行，每行輸出一組解，即所選取的數字，按照輸入中的順序排列。
　　若有多組解，優先輸出不包含第n個整數的；若都包含或都不包含，優先輸出不包含第n-1個整數的，依次類推。
　　最后一行輸出總方案數。

樣例輸入

5
-7 -3 -2 5 9
0

樣例輸出

-3 -2 5
-7 -2 9
2

數據規模和約定

　　1<=n<=22
　　T<=maxlongint

　　集合中任意元素的和都不超過long的范圍

?

?

#include <iostream> using namespace std; int visited[22];//用來記錄節點是否被訪問過 int seq[22];//用來盛放序列 int n,ans,cnt=0;//n表元素個數，ans是結果，cnt是結果的個數 void backtrack(int t)//因為題目要求先輸出不包含第n個元素的所以數組要倒著遍歷 { if(t<0) { int sum=0,sumofv=0; for(int i=0;i<n;i++) { if(visited[i]) sum+=seq[i]; sumofv+=visited[i];//用來看是否所有節點都未被訪問過 } if(sum==ans&&sumofv)//如果序列中有節點被訪問過，并且和是題目要求的就輸出 { for(int i=0;i<n;i++) if(visited[i]) cout<<seq[i]<<" "; cout<<endl; cnt++;//解的個數要++ } return; } for(int i=0;i<=1;i++) { visited[t]=i; backtrack(t-1); } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>seq[i]; cin>>ans; backtrack(n-1); cout<<cnt<<endl; return 0; }

?

轉自這個博客

最近自己很不在狀態，不能靜下心來敲代碼，敲不出來，只能轉自別人的博客。

?

?

總結

以上是生活随笔為你收集整理的算法训练 和为T 深度搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。