Solution of Challenge - 10

import java.util.ArrayList;

public class Problem10 {

    private static int TARGET_SUM = 100;

    private static int[] VALUES = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    static ArrayList add(int digit, String sign, ArrayList branches) 

    {

        for (int i = 0; i < branches.size(); i++) 

        {

            branches.set(i, digit + sign + branches.get(i));

        }

        return branches;

    }

    static ArrayList f(int sum, int number, int index)

    {

        int digit = Math.abs(number % 10);

        if (index >= VALUES.length) 

        {

            if (sum == number) {

                ArrayList result = new ArrayList();

                result.add(Integer.toString(digit));

                return result;

            }

            else 

            {

                return new ArrayList();

            }

        }

        ArrayList branch1 = f(sum - number, VALUES[index], index + 1);

        ArrayList branch2 = f(sum - number, -VALUES[index], index + 1);

        int concatenatedNumber = number >= 0

            ? 10 * number + VALUES[index]

            : 10 * number - VALUES[index];

        ArrayList branch3 = f(sum, concatenatedNumber, index + 1);

        ArrayList results = new ArrayList();

        results.addAll(add(digit, "+", branch1));

        results.addAll(add(digit, "-", branch2));

        results.addAll(add(digit, "", branch3));

        return results;

    }

    public static void main(String[] args)

   {

        for (Object string : f(TARGET_SUM, VALUES[0], 1)) 

        {

            System.out.println(string);

        }

    }

}

Explanation

I think it looks harder than it really is. To solve it, I'd try to decompose the problem into smaller problems (you know, the classic Divide and conquer).

So let's start with what we know:

• f(1..9) = 100

Here f is the function that returns our final equation. From here we can break this into 3 other pieces:

• 1 + f(2..9) = 100
• 1 - f(2..9) = 100
• f(12, 3..9) = 100

The first equation uses an addition, the second uses subtraction, and the third equation concatenates the first two numbers. From here, we get the following:

• f(2..9) = 100 - 1 = 99
• f(-2, 3..9) = 100 - 1 = 99
• f(12, 3..9) = 100

(Note how I moved the negative sign into the function on the second equation to keep the result the same.)

From here, we can keep working on each one of the equations above doing the same process:

• 2 + f(3..9) = 99
• 2 - f(3..9) = 99
• f(23, 4..9) = 99
• -2 + f(3..9) = 99
• -2 - f(3..9) = 99
• f(-23, 4..9) = 99
• 12 + f(3..9) = 100
• 12 - f(3..9) = 100
• f(123, 4..9) = 100

You'd have to keep doing this until you completely eliminate the function f. From there, each branch where the equality holds represents a solution to the problem, so you can backtrack your steps to stitch the resultant equation together.