Java program to find out all possible expressions to insert '+' and '-' in between values 1..to ..9 so that the given sum of the expression remains constant ....like below

/*
Write a program that outputs all possibilities to put + or - or nothing between the numbers 1, 2, ..., 9 (in this order) such that the result is always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100

*/

       
import java.util.ArrayList;
import java.util.Iterator;

public class TestIt {

 private static int SUM = 200;
 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);
  //System.out.println(digit);
  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) {

  Iterator < String > itr = f(SUM, values[0], 1).listIterator();
  //for (String string :f(TARGET_SUM, VALUES[0], 1))
  if (itr.hasNext()) {
   System.out.println(itr.next());
  }

 }
}