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 <= 3 && sum == Integer.parseInt(numbers)) {
return 0;
}

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

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 <= 3 && 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 && 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;.

StackExchange Code Review Q#113869, answer score: 3