// ----------------------------------------------------------------
// Imports
// ----------------------------------------------------------------

import java.util.StringTokenizer;

// ----------------------------------------------------------------
// ChosenSum
// ----------------------------------------------------------------

public class ChosenSum
{
   // ----------------------------------------------------------------
   // getTokens - Break 's' into tokens ('+' and '-' are delimiters)
   //             and return as an array
   // ----------------------------------------------------------------

   public static String[] getTokens(String s)
   {
      StringTokenizer tokenizer = new StringTokenizer(s, "+-", true);

      String[] tokens = new String[tokenizer.countTokens()];

      int i = 0;

      while(tokenizer.hasMoreTokens())
         tokens[i++] = tokenizer.nextToken();

      return(tokens);
   }

   // ----------------------------------------------------------------
   // evaluate - Return the result of evaluating 's' as if it
   //            were an arithmetic expression.  So, for example,
   //            "1+2+3-4" would result in 2 being returned.
   // ----------------------------------------------------------------

   public static int evaluate(String s)
   {
      String[] tokens = getTokens(s);

      int     sum   = 0;
      boolean doAdd = true;

      for(int i = 0; i < tokens.length; i ++)
      {
         if(i % 2 == 0)
            sum += (doAdd ? 1 : -1) * Integer.parseInt(tokens[i]);

         else
            doAdd = tokens[i].equals("+");
      }

      return(sum);
   }

   // ----------------------------------------------------------------
   // showSolutions - Find and display all ways to combine 'numbers'
   //                 such that the result is 'goal'.
   // ----------------------------------------------------------------

   public static void showSolutions(int[] numbers, int goal)
   {
      int      count   = 0;
      String[] symbols = { "+", "-", "" };
      int[]    indices = new int[numbers.length - 1];

      for(int i = 0; i < indices.length; i ++)
         indices[i] = 0;

      String fmt = "%-" + (2 * numbers.length - 1) + "s";

      for(;;)
      {
         String theString = "";

         for(int i = 0; i < numbers.length; i ++)
         {
            theString += numbers[i];

            if(i + 1 < numbers.length)
               theString += symbols[indices[i]];
         }

         if(evaluate(theString) == goal)
         {
            System.out.printf(fmt + " = %d\n", theString, goal);
            count++;
         }

         int current = indices.length - 1;

         while(current >= 0)
         {
            if(indices[current] + 1 < symbols.length)
            {
               ++indices[current];
               break;
            }

            indices[current--] = 0;
         }

         if(current < 0)
            break;
      }

      System.out.printf("-------------------\n");
      System.out.printf("Total Solutions: %d\n\n", count);
   }

   // ----------------------------------------------------------------
   // main
   // ----------------------------------------------------------------

   public static void main(String[] args)
   {
      int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
      int[] sums    = { 1, 5, 9, 11, 23, 27, 45, 54, 63, 100 };

      for(int sum : sums)
         showSolutions(numbers, sum);
   }
}