N个数字的所有可能组合以求和X

本文介绍了N个数字的所有可能组合以求和X的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我必须编写一个给定 n ， target 和 max 的程序，并返回大小为 n 等于 target ，其中任何数字都不能大于 max

I have to write a program that given n, target and max, returns all the number combinations of size n that sums to target, where no number can be greater than max

示例:

target = 3 max = 1 n = 4

输出:

[0, 1, 1, 1] [1, 0, 1, 1] [1, 1, 0, 1] [1, 1, 1, 0]

这是一个非常简单的示例，但是对于更复杂的情况，可能会有很多可能的组合.

It is a very simple example, but there can be a very large set of possible combinations for a more complex case.

我正在寻找任何算法线索，但是Java实现将是完美的.

I'm looking for any algorithmic clue, but a Java implementation would be perfect.

推荐答案

以下是Java版本:

import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class Main { public static void main(String[] args) { List<int[]> solutions = generate(3, 1, 4); for(int[] c: solutions) { System.out.println(Arrays.toString(c)); } } public static List<int[]> generate(int target, int max, int n) { return generate(new ArrayList(), new int[0], target, max, n); } private static List<int[]> generate(List<int[]> solutions, int[] current, int target, int max, int n) { int sum = Arrays.stream(current).sum(); if (current.length == n) { if (sum == target) { solutions.add(current); } return solutions; } if (sum > target) { return solutions; } for(int i=0; i <= max; i++) { int[] next = Arrays.copyOf(current, current.length + 1); next[current.length] = i; generate(solutions, next, target, max, n); } return solutions; } }