Question

link

Given a string of numbers, eg. “43868643”. Put ‘+’ and ‘-’ in between, and build an expression.

Solution

Iterate thru the input string and do DFS recrusively.

At each position, there’s 3 possibilities: plus, minus or do not skip.

Code

public List<String> solve(String str) {
    if (str == null || str.length() == 0) {
        return null;
    }
    List<String> result = new ArrayList<String>();
    helper(result, "", 0, str);
    Collections.sort(result);
    return result;
}

private void helper(List<String> result, String curExp, int curVal, String remain) {
    if (curVal == Integer.parseInt(remain)) {
        result.add(curExp + "=" + remain);
    } else if (curVal + Integer.parseInt(remain) == 0) {
        result.add(curExp + "=-" + remain);
    }
    for (int i = 1; i < remain.length(); i++) {
        String nextStr = remain.substring(0, i);
        int nextNum = Integer.parseInt(nextStr);

        // case 1: add a + between curExp and nextStr
        String newExp = curExp + "+" + nextStr;
        int newVal = curVal + nextNum;
        helper(result, newExp, newVal, remain.substring(i));

        // case 2: '-' sign
        newExp = curExp + "-" + nextStr;
        newVal = curVal - nextNum;
        helper(result, newExp, newVal, remain.substring(i));
    }
}

Testing

Input is 4312
Print the list: 
+4-3+1=2
-4+3-1=-2

Input is 43868643
Print the list: 
+4+3+8+6-8-6-4=3
+4+3+8-6-8+6-4=3
+4+3+86-86-4=3
+4+3-8+6+8-6-4=3
+4+3-8+68-64=3
+4+3-8-6+8+6-4=3
+4+3-86+86-4=3
+4-3+8+6-8-6-4=-3
+4-3+8-6-8+6-4=-3
+4-3+86-86-4=-3
+4-3-8+6+8-6-4=-3
+4-3-8+68-64=-3
+4-3-8-6+8+6-4=-3
+4-3-86+86-4=-3
+43+8+6-8-6=43
+43+8-6-8+6=43
+43+86-86=43
+43-8+6+8-6=43
+43-8-6+8+6=43
+43-86+86=43
-4+3+8+6-8-6+4=3
-4+3+8-6-8+6+4=3
-4+3+8-68+64=3
-4+3+86-86+4=3
-4+3-8+6+8-6+4=3
-4+3-8-6+8+6+4=3
-4+3-86+86+4=3
-4-3+8+6-8-6+4=-3
-4-3+8-6-8+6+4=-3
-4-3+8-68+64=-3
-4-3+86-86+4=-3
-4-3-8+6+8-6+4=-3
-4-3-8-6+8+6+4=-3
-4-3-86+86+4=-3
-43+8+6-8-6=-43
-43+8-6-8+6=-43
-43+86-86=-43
-43-8+6+8-6=-43
-43-8-6+8+6=-43
-43-86+86=-43