给定多个范围，请选择数字组合以达到给定的总和

要从匹配给定总和的数字数组中找到数字的给定排列，可以使用蛮力算法找到可能的组合。为此，您可以在构建中使用深度优先搜索，方法是一次从每个数组中选择一个数字来构建路径。

对于示例输入{ [1-6], [3-6], [2-5] }（包括结尾），有效路径可能是1 > 3 > 2（每个数组的第一个数字）。使用递归，您可以评估所有可能的路径并找到与给定总和匹配的路径。

首先，一些定义使用Java记录语法以避免不必要的样板代码。如果需要，可以将类反向移植到较低的Java版本。

// input range to pick numbers from
public record Range(int startInclusive, int endInclusive) {

    @Override
    public String toString() {
        return "[" + startInclusive + "," + endInclusive + "]";
    }
}

// a node in the graph contains the picked number and the range
// that this number has been picked from
public record Node(Range range, int number) {
    
    @Override
    public String toString() {
        return number + " from " + range.toString();
    }
}

// connection of multiple nodes in a graph
public record Path(Collection<Node> nodes) {

    public static Path EMPTY = new Path(Collections.emptyList());

    // sum of all current nodes
    public int sum() {
        int sum = 0;
        for (Node s : nodes()) {
            sum += s.number;
        }
        return sum;
    }

    // copy of this path with the node added
    public Path with(Node node) {
        List<Node> nodes = new ArrayList<>(nodes());
        nodes.add(node);
        return new Path(nodes);
    }
}

现在，PathContext它存储递归期间使用的必要信息。

public class PathContext {

    private final Range[] ranges;
    private final int sum;

    // resulting paths that match the sum
    private final Collection<Path> paths = new ArrayList<>();
    // find all matches or just one (latter is faster)
    private final boolean skipAfterMatch = false;

    public PathContext(Collection<Range> ranges, int sum) {
        this.ranges = ranges.toArray(new Range[0]);
        this.sum = sum;
    }

    // if the path a valid solution, add it the the results
    public void validatePath(Path path) {
        if (path.sum() == sum) {
            paths.add(path);
        }
    }

    public Range[] getRanges() {
        return ranges;
    }

    public Collection<Path> getPaths() {
        return Collections.unmodifiableCollection(paths);
    }

    public int getSum() {
        return sum;
    }
    
    public boolean abortSearch() {
        return skipAfterMatch && !paths.isEmpty();
    }
}

现在最后，dfs（深度优先搜索）：

public static void dfs(PathContext ctx, int rangeIdx, Path path) {
    // if we have no more ranges to pick from, validate if the sum matches
    if (rangeIdx >= ctx.getRanges().length) {
        ctx.validatePath(path);
    } else {
        // get the next range
        Range next = ctx.getRanges()[rangeIdx];

        // traverse trough all numbers in the range, end inclusive
        for (int i = next.startInclusive; i <= next.endInclusive; i++) {
            // generate a new node and path
            Node node = new Node(next, i);
            Path newPath = path.with(node);

            // recurse with the next range
            dfs(ctx, rangeIdx + 1, newPath);

            // check if the search can be aborted (if only one match is needed)
            if (ctx.abortSearch()) {
                break;
            }
        }
    }
}

然后，您可以dfs使用示例数据进行呼叫：

public static void main(String[] args) {
    Range range1 = new Range(1, 6);
    Range range2 = new Range(3, 6);
    Range range3 = new Range(2, 5);
    List<Range> ranges = List.of(range1, range2, range3);

    PathContext ctx = new PathContext(ranges, 13);
    // start from index 0 (the first range)
    dfs(ctx, 0, Path.EMPTY);

    // output logging
    System.out.println("total sum: " + ctx.getSum());
    for (Path path : ctx.getPaths()) {

        for (Node node : path.nodes()) {
            System.out.println(node);
        }
        System.out.println();
    }
}

结果输出为：

total sum: 13
2 from [1,6]
6 from [3,6]
5 from [2,5]

3 from [1,6]
5 from [3,6]
5 from [2,5]

3 from [1,6]
6 from [3,6]
4 from [2,5]

4 from [1,6]
4 from [3,6]
5 from [2,5]

4 from [1,6]
5 from [3,6]
4 from [2,5]

4 from [1,6]
6 from [3,6]
3 from [2,5]

5 from [1,6]
3 from [3,6]
5 from [2,5]

5 from [1,6]
4 from [3,6]
4 from [2,5]

5 from [1,6]
5 from [3,6]
3 from [2,5]

5 from [1,6]
6 from [3,6]
2 from [2,5]

6 from [1,6]
3 from [3,6]
4 from [2,5]

6 from [1,6]
4 from [3,6]
3 from [2,5]

6 from [1,6]
5 from [3,6]
2 from [2,5]