获取所有可能的总和为一个给定的数字

小编典典

获取所有可能的总和为一个给定的数字

algorithm

我正在为Android开发数学应用程序。在这些字段之一中，用户可以输入一个整数（无数字且大于0）。这个想法是获取所有可能的和，使之成为整数，而不加倍（在这种情况下为4
+ 1 == 1 + 4）。唯一已知的是此int。

例如：

假设用户输入4，我希望该应用返回：

4
3 + 1
2 + 2
2 + 1 + 1
1 + 1 + 1 + 1

显然4 == 4，所以也应该加上。关于我应该如何做的任何建议？

阅读 183

2020-07-28

共1个答案

小编典典

这是一个简单的算法，旨在做到这一点

来自：http
:
//introcs.cs.princeton.edu/java/23recursion/Partition.java.html

public class Partition {

    public static void partition(int n) {
        partition(n, n, "");
    }
    public static void partition(int n, int max, String prefix) {
        if (n == 0) {
            StdOut.println(prefix);
            return;
        }

        for (int i = Math.min(max, n); i >= 1; i--) {
            partition(n-i, i, prefix + " " + i);
        }
    }


    public static void main(String[] args) {
        int N = Integer.parseInt(args[0]);
        partition(N);
    }

}

2020-07-28