// 我真誠地保證：
// 我自己獨立地完成了整個程序從分析、設計到編碼的所有工作。
// 如果在上述過程中，我遇到了什么困難而求教于人，那么，我將在程序實習報告中
// 詳細地列舉我所遇到的問題，以及別人給我的提示。
// 我的程序里中凡是引用到其他程序或文檔之處，
// 例如教材、課堂筆記、網上的源代碼以及其他參考書上的代碼段,
// 我都已經在程序的注釋里很清楚地注明了引用的出處。
// 我從未沒抄襲過別人的程序，也沒有盜用別人的程序，
// 不管是修改式的抄襲還是原封不動的抄襲。
// 我編寫這個程序，從來沒有想過要去破壞或妨礙其他計算機系統的正常運轉。
// 學生：朱詩雄

/*
	文件名稱：	bag
	項目名稱：	背包問題
	創建者：	朱詩雄
	文件中的函數名稱和簡單功能描述：
		int bag(int *w,int n,int t) 給出n個背包，重量存儲在w數組里，總重量為t，判斷是否有解

	輸入格式：第一行輸入背包數目n，第二行輸入這n個背包的重量，第三行輸入總重量t。
	例：
	5
	1 5 3 8 5
	7
	輸出：
	one of answers is:no answer.
*/
#include<iostream>
using namespace std;

//求背包問題的遞歸函數
int bag(int *w,int n,int t);

int main()
{
	int n;					//背包數量
	cin>>n;
	int *w;
	w=new int [n];
	for(int i=0;i<n;i++)
		cin>>w[i];			//輸入背包重量
	int t;					//總重量T		
	cin>>t;	
	cout<<"one of answers is:";
	if(bag(w,n,t)==0) cout<<"no answer.";
	cout<<endl;
	return 0;
}

int bag(int *w,int n,int t)
{
	int i;
	for(i=n-1;i>=0;i--)			
		if((t-w[i])>=0)
		{
			if((t-w[i])==0 || bag(w,i,t-w[i])==1)  //背包問題有解的條件
			{
				cout<<w[i]<<' ';		//輸出一個可行解
				return 1;
			}
		}
	return 0;
}