采用整数并返回所有可能的加法格式的算法
我需要编写一个采用整数的算法并返回所有可能的加法格式
例如
如果我得到：6
它将返回以下字符串：
0+6=6 1+1+1+1+1+1=6 1+1+1+1+2=6 1+1+1+3=6 1+1+4=6 1+5=6 2+1+1+1+1=6 2+1+1+2=6 2+1+3=6 2+4=6 3+1+1+1=6 3+1+2=6 3+3=6 4+1+1=6 4+2=6 5+1=6 6+0=6 这是我的尝试：
import java.util.*; public class Test { public static void main(String[] args) { Scanner in = new Scanner(System.in); System.out.print("Enter an integer? "); int num = in.nextInt(); System.out.println(); calculate(num); } private static void calculate(int n) { int[] arInt = new int[n]; for(int i = 0; i <= n; i++) { for(int j = 0; j <= n; j++) { arInt[j] = i; } // ... } } }
我同意布拉德的观点。 完成此操作的最佳方法可能是通过递归。 事实上，我昨晚正在研究与此有关的事情。 我使用递归回溯算法解决了我的问题。 查看维基百科页面： 回溯
现在，我不保证没有更好，更简单的方法来解决这个问题。 但是，通过递归回溯，您将找到所有解决方案。
有一点要注意，那就是0.你可以将任意数量的零投入加法/减法，它将会出现相同的结果。
如果你问这个问题，你可能会被卡住……所以我给你一个提示：
通常，在这种问题中，您不会将具有不同排列的相同组合视为不同的计数，并且您不会将加法视为0：请参阅分区 。 但是，在你的例子中，你似乎区分了不同的排列并计算0.我非常确定你不应该包含0，因为这将为你提供无数的n个例子。 （顺便说一句，你给出的答案并不包括所有的计数。）所以我假设你区分不同的排列，但不允许段变为0.这实际上使问题更容易。
假设你有n = 6。
OOOOOO ^ ^ ^ ^ ^
想想上面六个物体之间的n – 1 = 5个位置。 对于每个职位，您可以决定是否分段。 例如，
O|OOO|OO ^ ^ ^ ^ ^
是一种可能的细分。 将其解释为：1 + 3 + 2，将连续的对象取为未被“|”分段。 您应该能够以这种方式获得所有可能的方式。 即，对于n-1个位置，是否分段。 对于任何n，您的列表应为2 ^（n-1）个示例。
例如，对于n = 3：1 + 1 + 1,2 + 1,1 + 2,3 => 4种不同方式= 2 ^（3-1）
对于n = 6，你应该有2 ^（6-1）= 32个例子，但你只有17个，它会立即告诉你的列表不完整。
最后请注意，正如我在开头所写的那样，你的问题与更加标准的分区问题不同。
它看起来像是一个家庭作业，所以我不会试着为你写。 但我会给你一个关于解决方案的提示。 你有固定的数量，想象例如大理石。 您正在尝试查找所有可能的数字，以计算该数量。 这意味着你必须以某种方式将大理石分成小组。 如果你知道基本的组合，你可以很容易地计算可能性并使用算法枚举它们。 祝你好运！
Java中使用递归的可能解决方案：
public void run(int n) { List combos = showAdditionsFor(n); for (StringBuilder s : combos) { if (s.indexOf("+") < 0) { System.out.println(s + " + 0 = " + n); System.out.println("0 + " + s + " = " + n); } else { System.out.println(s + " = " + n); } } } List showAdditionsFor(int n) { List list = new ArrayList (); if (n == 0) list.add(new StringBuilder("")); else if (n == 1) list.add(new StringBuilder(String.valueOf(1))); else { for (int i = 1; i <=n; i++) { //get ni list List tempList = showAdditionsFor(ni); appendToEachListElement(String.valueOf(i),tempList); list.addAll(tempList); } } return list; } private void appendToEachListElement(String x, List l) { for (StringBuilder s : l) { if (s.length() == 0) s.append(x); else s.append("+" + x); } }