Quick Sum TopCoder (Brute Force solution) Given a string of digits, find the minimum number of additions
  required for the string to equal some target number. Each addition is
  the equivalent of inserting a plus sign somewhere into the string of
  digits. After all plus signs are inserted, evaluate the sum as usual.
  For example, consider the string "12" (quotes for clarity). With zero
  additions, we can achieve the number 12. If we insert one plus sign
  into the string, we get "1+2", which evaluates to 3. So, in that case,
  given "12", a minimum of 1 addition is required to get the number 3.
  As another example, consider "303" and a target sum of 6. The best
  strategy is not "3+0+3", but "3+03". You can do this because leading
  zeros do not change the result.
  
  Write a class QuickSums that contains the method minSums, which takes
  a String numbers and an int sum. The method should calculate and
  return the minimum number of additions required to create an
  expression from numbers that evaluates to sum. If this is impossible,
  return -1.
  
  TopCoder link


So I came up with a brute force solution of checking all possible solutions to find the min. Is there a better way to do this?

public class QuickSums {

  public static void main(String args[]) {
    String input = "99999";
    int total = 45;
    int res = minSums(input, total);
    System.out.println(res);
  }

  // With at most 10 digits(constraint given), there are at most 2^9 ways to insert plus signs into the string.
  // Therefore, there are at most 2^9 possibilities to consider. We can use recursion to go through
  // all possibilities and keep track of the minimum number of additions required
  public static int minSums(String numbers, int sum) {
    int N = numbers.length();

    // base cases
    if (N &lt;= 3 &amp;&amp; sum == Integer.parseInt(numbers)) {
      return 0;
    }

    else if (N == 2 &amp;&amp; Integer.parseInt(numbers.substring(0, N - 1))
        + Integer.parseInt(numbers.substring(N - 1)) == sum) {
      return 1;
    } else if (N == 2 &amp;&amp; Integer.parseInt(numbers.substring(0, N - 1))
        + Integer.parseInt(numbers.substring(N - 1)) != sum) {
      return -1;
    }
    else if (N == 1 &amp;&amp; Integer.parseInt(numbers) != sum) {
      return -1;
    }

    // solution
    else {

      int lenOFStr = N-1;
      int possibleCombination = (int) Math.pow(2, lenOFStr);

      // numbers will contain between 1 and 10 characters, inclusive.
      int min = Integer.MAX_VALUE;
      StringBuilder tempString;
      for (int i = 0; i &lt; possibleCombination; i++) {
        String plus = Integer.toBinaryString(i);
        while (plus.length() &lt; lenOFStr) {
          plus = "0" + plus;
        }
        // System.out.println(plus);

        // Add plus sign to the string
        tempString = new StringBuilder(numbers);
        int len = N;
        for (int k = 0; k &lt; lenOFStr ; k++) {
          if (plus.charAt(k) == '1') {
            len = len + 1;
            int offset = len-N+k;
           // System.out.println(offset);
            tempString.insert(offset, " ");
          }
        }
        // System.out.println(tempString);

        // compute the sum
        String[] arr = tempString.toString().split(" ");
        long tempSum = 0;
        for (String s : arr) {
          tempSum +=Long.parseLong(s);
        }

        // check if the sum is same
        if (tempSum == sum) {
          min = Math.min(arr.length-1, min);
        }


      }
      return (min == Integer.MAX_VALUE) ? -1 : min;

    }
  }

}


This program works fine for all inputs but I'm wondering, there must be a dynamic programming solution to this? Or something better?
public static int minSums(String numbers, int sum) {
  int N = numbers.length();  



variables should be named using camelCase casing so n would be better, but what does N/n represent ? Its the number of digits contained in the String numbers which isn't named correctly because there is only one number passed which consists of multiple digits. So a better way would be like so  

public static int minSums(String number, int sum) {
  int digits = number.length();   


but as the default indentation is 4 spaces this should be like so  

public static int minSums(String number, int sum) {
    int digits = number.length();  




This if..else if..else construct can be simplified because for the first cases you are returning a value the else if..else aren't needed and will save some horizontal spacing if removed. You should have the two cases where you check for N == 2 into one single if with a nested if..else like so  

// changed N to digits

if (digits &lt;= 3 &amp;&amp; sum == Integer.parseInt(numbers)) {
    return 0;
}

if (digits == 2) {
    if (Integer.parseInt(numbers.substring(0, N - 1))
       + Integer.parseInt(numbers.substring(N - 1)) == sum) {
        return 1;      
    } else {
        return -1;      
    }
}

if (digits == 1 &amp;&amp; Integer.parseInt(numbers) != sum) {
  return -1;
}

// solution




Commented out code is dead code and should be removed because it is only adding noise to the code which decreases readability.  



Let your variables and operators have some space to breathe. Something like int offset = len-N+k; isn't just as readable as int offset = len -N + k;.