N个数字的所有可能组合以求和X [英] All possible combination of N numbers to sum X

问题描述

我必须编写一个给定 n ， target 和 max 的程序，并返回大小为 n <的所有数字组合/code>等于 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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！