package kata;

import java.util.*;

/**
 * https://leetcode.com/problems/expression-add-operators/
 *
 * <p>Given a string that contains only digits 0-9 and a target value, return
 * all possibilities to add binary operators (not unary) +, -, or * between the
 * digits so they evaluate to the target value.
 */
public class ExpressionAddOperators {
  static List<String> expressionAddOperators(String s, int t) {
    int n = s.length();
    if (n == 0) {
      return List.of();
    }

    List<String> output = new ArrayList<>();
    LinkedList<String> soFar = new LinkedList<>();
    recurse(0, 0, 0, 0, s, t, s.length(), soFar, output);
    return output;
  }

  static void recurse(int index, int prevOp, int curOp, int val, String s, int t, int n, LinkedList<String> soFar, List<String> output) {
    if (index == n) {
      if (curOp == 0 && val == t) {
        StringBuilder sb = new StringBuilder();
        soFar.stream().forEach(op -> sb.append(op));
        output.add(sb.toString());
      }
      return;
    }

    char c = s.charAt(index);
    curOp = curOp * 10 + Character.getNumericValue(c);

    // Treat s[index] as an extra digit of the current value
    if (curOp > 0) {
      recurse(index + 1, prevOp, curOp, val, s, t, n, soFar, output);
    }

    // Try "+"
    if (!soFar.isEmpty()) {
      soFar.addLast("+");
    }
    
    String opStr = Integer.toString(curOp);
    soFar.addLast(opStr);
    recurse(index + 1, curOp, 0, val + curOp, s, t, n, soFar, output);
    soFar.removeLast();
    if (!soFar.isEmpty()) {
      soFar.removeLast();
    }

    if (!soFar.isEmpty()) {
      // Try '-'
      soFar.addLast("-");
      soFar.addLast(opStr);
      recurse(index + 1, -curOp, 0, val - curOp, s, t, n, soFar, output);
      soFar.removeLast();
      soFar.removeLast();

      // Try '*'
      soFar.addLast("*");
      soFar.addLast(opStr);
      recurse(
          index + 1,
          curOp * prevOp,
          0,
          val - prevOp + (curOp * prevOp),
          s,
          t,
          n,
          soFar,
          output);
      soFar.removeLast();
      soFar.removeLast();
    }
  }

  public static void main(String args[]) {
    runSample("123", 6);
    // Output: ["1+2+3", "1*2*3"]

    runSample("232", 8);
    // Output: ["2*3+2", "2+3*2"]

    runSample("105", 5);
		// Output: ["1*0+5","10-5"]

    runSample("00", 0);
		// Output: ["0+0", "0-0", "0*0"]

    runSample("123", 123);
    // Output: ["123"]
    //
    runSample("1234", 46);
    // Output: ["12+34"]

    runSample("3456237490", 9191);
		// Output: []
	}

  static void runSample(String s, int target) {
    System.out.printf("%s, %s = %s\n", s, target, expressionAddOperators(s, target));
  }
}

@@ -1272,18 +1272,222 @@
     
-// Try %22+%22
+String opStr = Integer.toString(curOp);%0A    if (soFar.isEmpty()) %7B%0A      soFar.addLast(opStr);%0A      recurse(index + 1, curOp, 0, val + curOp, s, t, n, soFar, output);%0A      soFar.removeLast();%0A      return;%0A    %7D%0A
 %0A   
@@ -1503,32 +1503,49 @@
 ar.isEmpty()) %7B%0A
+      // Try %22+%22%0A
       soFar.addL
@@ -1560,61 +1560,8 @@
 ;%0A  
-  %7D%0A    %0A    String opStr = Integer.toString(curOp);%0A
     
@@ -1578,24 +1578,26 @@
 ast(opStr);%0A
+  
     recurse(
@@ -1655,24 +1655,26 @@
 utput);%0A    
+  
 soFar.remove
@@ -1689,92 +1689,30 @@
     
-if (!soFar.isEmpty()) %7B%0A      soFar.removeLast();%0A    %7D%0A%0A    if (!soFar.isEmpty()) %7B
+  soFar.removeLast();%0A
 %0A   
@@ -2672,16 +2672,70 @@
 tput: %5B%5D
+%0A%0A    runSample(%221234%22, 1234);%0A    // Output: %5B%221234%22%5D
 %0A%09%7D%0A%0A  s

make it easier to understand