java - 把一个整数分成k份

Question

我正在用 Java 编程，我需要制定一个算法。该算法的要求是:

• 我们有 3 个整数变量 n, m, k;
• 我们想将n分成k部分，这样k部分的总和等于n，每个部分都是1和m之间的整数。
• 我们需要所有可能的整数组合。

例如输入集:

n = 7; m = 3; k = 4

我们可以制定两种不同的组合:

7 = 2 + 2 + 2 + 1

和

7 = 3 + 2 + 1 + 1

谢谢大家

Answer 1

这个想法是一种回溯算法方法(使用递归)，您可以减少参数并获得部分解决方案，然后检查您是否有正确的解决方案。

public class Problem {

    private static void algorithm(int n, int k, int m) {
        algorithmRecursive(Collections.EMPTY_LIST, n, k, m, 1);
    }

    private static void algorithmRecursive(List<Integer> partial, int n, int k, int m, int min) {
        if ( (k > 0) ) {
            // Optimization
            if ((n <= k * m) && (n >= k*min)){
                for (int i = min; i <= Math.min(m, n); i++) {
                    List<Integer> newPartial = new ArrayList<>(partial);
                    newPartial.add(i);
                    algorithmRecursive(newPartial, n - i, k - 1, m, i);
                }
            }
        } else if (n == 0) {
            // Right solution
            System.out.println(partial);
        }
    }

    public static void main(String[] args) {
        algorithm(7,4,3);
    }
}