Algorithm that takes an integer and returns all possible format of addition

I need to write an algorithm that takes an integer and returns all possible format of addition

e.g.

If I eneter: 6

it would return the following String:

 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

Here is my try:

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++)
        {
   开发者_如何学JAVA         for(int j = 0; j <= n; j++)
            {
                arInt[j] = i;
            }
            // ...
        }
    }
}

---

I agree with Brad. The best way to complete this would probably be through recursion. In fact, I was working on something related to this last night. I solved my problem using a recursive backtracking algorithm. Check out the Wikipedia page: Backtracking

Now, I make no guarantees that there aren't better, less complex ways to solve this. However, with recursive backtracking you will find all the solutions.

One thing to watch out for though, that 0. You can throw any amount of zeros into an addition/subtraction and it will come out the same.

---

If you asked the question, you are probably stuck... so i give you a hint :

---

Usually, in this kind of problem, you do not consider the same combinations with different permutations as different counts, and you do not consider addtion by 0: see Partition. However, in your example, you seem to be distinguishing different permutations and counting 0. I am pertty much sure that you are not supposed to include 0 because that will give you infinitely many examples to any n. (By the way the answer you gave does not include all counts.) So I assume that you distinguish different permutations but not allow segment into 0. That actually makes the problem much easier.

Suppose you have n = 6.

   O O O O O O 
    ^ ^ ^ ^ ^

Think about the n - 1 = 5 positions between the six objects above. For each position, you can decide to either segment at the point or not. For example,

   O|O O O|O O 
    ^ ^ ^ ^ ^

is one possible segmentation. Interpret this as: 1+3+2, taking the consecutive objects not segmented by '|'. You should be able to get all possible ways in this way. Namely, for n-1 positions, either segment it or not. For any n, your list should be of 2^(n-1) examples.

E.g. for n = 3: 1+1+1, 2+1, 1+2, 3 => 4 different ways = 2^(3-1)

for n = 6, you should have 2^(6-1) = 32 examples, but you only have 17, which immediately tells that your list is not complete.

Finally note that, as I wrote at the beginning, your question is different from the partion question which is much more standard.

---

It looks like a homework, so I won't try to write it for you. But I will give you a hint about the solution. You have fixed quantity, imagine e.g. marbles. You are trying to find all possible numbers that add up to that quantity. This means you have to divide the marbles into groups somehow. If you know basic combinatorics, you can easily count the possibilities and enumerate them using an algorithm. Good luck!

---

Possible solution in Java using recursion:

public void run(int n)
{

    List<StringBuilder> 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<StringBuilder> showAdditionsFor(int n)
{
    List<StringBuilder> list = new ArrayList<StringBuilder>();
    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 n-i list
            List<StringBuilder> tempList = showAdditionsFor(n-i);
            appendToEachListElement(String.valueOf(i),tempList);
            list.addAll(tempList);
        }
    }

    return list;
}


private void appendToEachListElement(String x, List<StringBuilder>l)
{
    for (StringBuilder s : l)
    {
        if (s.length() == 0)
            s.append(x);
        else
            s.append("+" + x);
    }

}