1.题目
https://pintia.cn/problem-sets/994805342720868352/problems/994805424153280512
求所有从根结点到叶子结点的路径，使得每条路径上结点的权值之和等于常数S。
如果存在多条这样的路径，则按照路径非递增顺序输出。
2.思路
（1）由于最后的输出要按权值从大到小排序，所以在读入时就事先对每个结点的子结点child进行排序，这样在遍历时就会优先遍历到权值大的子结点。
（2）递归过程中保存路径：使用path[]数组表示路径 或者 使用vector。
后者：当枚举当前访问结点的子结点的过程中，就可以先使用push_back()将子结点加入路径中，然后往下一层递归。最后在下一层递归回溯上来之前讲前面加入的子结点pop_back()即可。
（3）递归出现sum==S时要判断当前访问结点是否为叶结点，如果不是则必须访问。
（4）cmp的所有情况都必须有返回值——因为程序需要能够处理两条路径上结点weight相同的情况。
3.完整代码
#include<vector> #include<algorithm> #include<iostream> #include<stdlib.h> #include<stdio.h> #include<cmath> using namespace std; const int maxn=110; int num;//既定的路径之和 struct node{ int data; vector<int>child;//孩子结点 }Node[maxn]; vector<int>path;//装入一条路径的所有结点 bool cmp(int a,int b){ return Node[a].data>Node[b].data; } void DFS(int index,int sum){ if(sum>num) return; if(sum==num){//注意还要判断是否为叶结点 if(Node[index].child.size()==0){//为叶子结点时就结算 printf("%d ",Node[index].data); for(int i=0;i<path.size();i++){//输出路径所有结点 printf(" %d",path[i]); } printf("\n"); }else return;//没到叶结点就直接返回 } for(int i=0;i<Node[index].child.size();i++){//遍历当前结点的所有结点 int childID=Node[index].child[i]; path.push_back(Node[childID].data);//别漏了 DFS(childID,sum+Node[childID].data); } } int main(){ int nodenum,nonleaf; scanf("%d%d%d",&nodenum,&nonleaf,&num); for(int i=0;i<nodenum;i++){ scanf("%d",&Node[i].data); } for(int i=0;i<nonleaf;i++){ int father,childnum; scanf("%d%d",&father,&childnum); for(int j=0;j<childnum;j++){ //scanf("%d",Node[i].child[i]); int cn; scanf("%d",&cn); Node[i].child.push_back(cn); } sort(Node[father].child.begin(),Node[father].child.end(),cmp);//从大到小排序 } path[0]=0; DFS(0,Node[0].data); system("pause"); }
