java - 获取加起来等于给定数字的所有可能的总和

Question

我正在为安卓开发一个数学应用。在这些字段之一中，用户可以输入一个 int(无数字且大于 0)。这个想法是获得所有可能的和，使这个 int，没有 double (在这种情况下为 4+1 == 1+4)。唯一已知的是这个 int。

例如:

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

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

显然 4 == 4 所以也应该添加。关于我应该如何着手做这件事有什么建议吗？

Answer 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);
    }

}