2019独角兽企业重金招聘Python工程师标准>>> 
1: 用数组链表来存储树
2: dfs找路径时， 每次递归dfs之后，要把push_back进去的节点退出去
for(int i = 0; i < cn; i++){//挨个child找下去node tmp = tree[t][i];dfs(tmp.id, sum, path);path.pop_back();//从dfs返回后， 退出当前的元素}3: 存储路径用vector<vecotr<int>>, 每次复制vector<int>可以直接用=
if(sum == s ){// 路径weight和满足了vector<int> vtmp = path; //vector可以用等号=直接复制！！！ res.push_back(vtmp);return;}自己到是能写出来，就是太慢了：
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;int n, m,s;typedef struct node{int id;int weight;
};vector<node> tree[100+5];//数组链表来存储树
int weight[100+5];
int isNonLeaf[100+5];//是否是非叶子节点bool cmp(const node a, const node b){return (a.weight>b.weight); //如果带上等号，用>=就会invalid operator运行错误，fuck!
}vector <vector<int>> res;vector<int> path;void dfs(int t, int sum, vector<int> v){sum += weight[t];path.push_back(weight[t]);if(isNonLeaf[t] == 0){//走到叶子节点了 if(sum == s ){// 路径weight和满足了vector<int> vtmp = path; //vector可以用等号=直接复制！！！ res.push_back(vtmp);return;}return;//无路可走，返回}int cn = tree[t].size();for(int i = 0; i < cn; i++){//挨个child找下去node tmp = tree[t][i];dfs(tmp.id, sum, path);path.pop_back();//从dfs返回后， 退出当前的元素}
}int main(){freopen("in.txt","r",stdin);scanf("%d%d%d",&n,&m,&s);for(int i = 0; i < n; i++){scanf("%d",&weight[i]);}memset(isNonLeaf, 0, sizeof(isNonLeaf));int nonLeaf, childCnt;for(int i = 0; i < m; i++){scanf("%d %d",&nonLeaf, &childCnt);if (childCnt > 0){isNonLeaf[nonLeaf] = 1;//有child,所以不是叶子for(int j = 0; j < childCnt; j++){node tmp;int id;scanf("%d", &id);tmp.id = id;tmp.weight = weight[id];tree[nonLeaf].push_back(tmp);}sort(tree[nonLeaf].begin(), tree[nonLeaf].end(),cmp);//排序，使得较大weight的子节点排在前面//test/*for(int i = 0; i < tree[nonLeaf].size(); i++){printf("%02d :%d\n", tree[nonLeaf][i].id, tree[nonLeaf][i].weight );}printf("\n");*/}}dfs(0, 0, path);for(int i = 0; i < res.size(); i++){for(int j = 0; j < res[i].size()-1; j++){printf("%d ",res[i][j]);}printf("%d\n", res[i][res[i].size()-1]);}return 0;
}