这道关于树形网络的算法的思路是什么呢?

Question

请问下面的题的思路是什么,其他地方如Leetcode上有没有相似的题目呢?

现有一树形网络,每个结点是一个设备,每个设备具有一个设备编号和一个管理容量值.
你的任务是:找出从根节点到叶结点的管理容量之和等于给定数值的所有路径.

输入:

• 第一行分别为结点个数N(<100),非叶子结点的个数M(<N),给定的总管理容量是S(<2^30);
• 第二行按结点编号顺序给出N个结点的管理容量
• 随后M行,每行按以下格式给出
  ID K ID[1] ID[2] ... ID[K-1] ID[K]
  其中ID是一个非叶子结点的2位数编号,K是其叶子结点个数,后面K个数字是一系列子节点的编号.

输入中出现的数值均为正整数
为简单起见,固定根结点的编号为00

输出:

• 找出所有管理容器之和为S的路径,并按非递增序输出.注:保证至少会有一条路径满足要求
• 每条路径占一行,输出从根结点到叶结点每个结点的管理容量.数字键以一个空格分隔.

样例:
输入:

20 9 24
10 2 4 3 5 10 2 18 9 7 2 2 1 3 12 1 8 6 2 2
00 4 01 02 03 04
02 1 05
04 2 06 07
03 3 11 12 13
06 1 09
07 2 08 10
16 1 15
13 3 14 16 17
17 2 18 19

输出:

10 5 2 7
10 4 10
10 3 3 6 2
10 3 3 6 2

提示
示例解释:
合计有4条可以满足总容量为24的要求,按照非递增排序:

1. 10 5 2 7的5大于10 4 10的4所以排第一个;同理,10 4 10排第二个
2. 10 3 3 6 2最后的2是18和19号结点,不分先后,但是两个都要输出.

代码

import java.nio.charset.StandardCharsets;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in, StandardCharsets.UTF_8.name());
        int nodeNum = scanner.nextInt();
        int nonLeafNodeNum = scanner.nextInt();
        int targetCapacity = scanner.nextInt();
        int[] capacity = new int[nodeNum];
        for (int i = 0; i < nodeNum; i++) {
            capacity[i] = scanner.nextInt();
        }
        NonLeafNode[] nonLeafNodes = new NonLeafNode[nonLeafNodeNum];
        for (int i = 0; i < nonLeafNodeNum; i++) {
            int nodeId = scanner.nextInt();
            int subNodeNum = scanner.nextInt();
            nonLeafNodes[i] = new NonLeafNode(nodeId, subNodeNum);
            for (int j = 0; j < subNodeNum; j++) {
                nonLeafNodes[i].subNodeIds[j] = scanner.nextInt();
            }
        }
        scanner.close();
        String[] path = getPathOfCapacity(capacity, nonLeafNodes, targetCapacity);
        if (null != path) {
            for (String p : path) {
                System.out.println(p);
            }
        }
    }

    static String[] getPathOfCapacity(int[] capacitys, NonLeafNode[] nonLeafNodes, int targetCapacity) {
        // TODO 在此补充你的代码
        return null;
    }

    static class NonLeafNode {
        int nodeId;
        int[] subNodeIds;

        public NonLeafNode(int nodeId, int subNodeNum) {
            this.nodeId = nodeId;
            this.subNodeIds = new int[subNodeNum];
        }
    }
}

Answer 1

leetcode上应该是有的，貌似可以用树的遍历+回溯来做。