共计 1238 个字符，预计需要花费 4 分钟才能阅读完成。
也不难，使用 DFS 就能很好的解决问题；对于 DFS 的途中节点记录有两种方法，这个需要注意一下:1. 使用 vector 模拟栈，每次递归的时候压栈或者弹栈，遇到符合要求的时候直接复制该栈保存；2. 使用 path 数组，并且利用 numnode 来追踪 path 数组的长度，其中 path[i] 代表路径上第 i 个节点的编号。由于 numnode 限制了 path 的长度，所以无需弹栈或者入站操作，只需要覆盖即可；
关于本题判断还有一个优化，就是在过程中每次 sum>s 直接弹出，比之前自己想判断叶子节点优化了不少；完整代码如下所示：
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
using std::vector;
const int maxn=110;
int n,m,s;
int path[maxn];
struct node{
int weight;
vector<int>child;
}table[maxn];
bool cmp(int a,int b){
return table[a].weight>table[b].weight;
}
void DFS(int index,int numNode,int sum){
if(sum>s)
return;
if(sum==s){
if(table[index].child.size()!=0)
return;
for(int i=0;i<numNode;i++){
printf(“%d”,table[path[i]].weight);
if(i<numNode-1)
printf(” “);
else
printf(“\n”);
}
return;
}
for(int i=0;i<table[index].child.size();i++){
path[numNode]=table[index].child[i];
DFS(table[index].child[i],numNode+1,sum+table[table[index].child[i]].weight);
}
}
int main(){
int root,leaf,num;
scanf(“%d%d%d”,&n,&m,&s);
for(int i=0;i<n;i++){
scanf(“%d”,&table[i].weight);
}
for(int i=0;i<m;i++){
scanf(“%d%d”,&root,&num);
for(int j=0;j<num;j++){
scanf(“%d”,&leaf);
table[root].child.push_back(leaf);
}
sort(table[root].child.begin(),table[root].child.end(),cmp);
}
path[0]=0;
DFS(0,1,table[0].weight);
system(“pause”);
return 0;
}
