本文介绍了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; } }更多推荐
N个数字的所有可能组合以求和X
发布评论