java - 使用此函数查找使用操作(+、- 和 concat)将数字 1 - 9 添加到总和的表达式时，我哪里出错了？

Question

有人可以帮忙修复这个错误吗？尝试编写一个函数，通过使用加法、减法或串联来生成一个数学表达式列表，这些数学表达式的值为 100，其中包含数字 1 到 9？我的添加和子分支正在工作。当我拉入串联路径时，它仅适用于某些测试用例？提前致谢。下面是我的代码。

对于我的数字 1-9 和总和为 100 的测试用例，有些表达式是错误的，有些是缺失的。这是我的输出:

• 1 + 2 + 3 + -4 + 5 + 6 + 78 + 9
• 1 + 2 + 34 + -5 + 67 + -8 + 9
• 1 + 23 + -4 + 5 + 6 + 78 + -9
• 1 + 23 + -4 + 56 + 7 + 8 + 9
• 12 + 3 + 4 + 5 + -6 + -7 + 89
• 12 + 3 + -4 + 5 + 67 + 8 + 9
• 12 + -3 + -4 + 5 + -6 + 7 + 89
• 123 + -4 + -5 + -6 + -7 + 8 + -9

• 123 + -35 + 6 + 7 + 8 + -9

  package domain;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  import java.util.Scanner;
  
  public class ExpressionFinder {
  
   Scanner s = new Scanner(System.in);
  
   public ArrayList<ArrayList<Integer>> getExpressions(int sum, int[] operands){
  
     ArrayList<ArrayList<Integer>> expressions = new ArrayList<ArrayList<Integer>>();
     ArrayList<Integer> sourceExpression = new ArrayList<Integer>();
     sourceExpression.add(operands[0]);
     findExpressions(expressions, sourceExpression, sum - operands[0], operands, 1);
     return expressions;
   }
  
   public static String getReadableExpression(List<Integer> operands){
      List<String> exp = new ArrayList<String>(operands.size());
  
      for(Integer op : operands)
         exp.add(String.valueOf(op));
  
      return String.join(" + ", exp);
   }
  
  private void findExpressions(ArrayList<ArrayList<Integer>> expressions, ArrayList<Integer> currentExpression, int sum, int[] operands, int current){
  
     if(current == operands.length){
         if(sum == 0)
             expressions.add(new ArrayList<>(currentExpression));
         return;
    }
  
   currentExpression.add(operands[current]);
   findExpressions( expressions, currentExpression, sum - currentExpression.get(currentExpression.size() - 1), operands, current + 1);
   currentExpression.remove(currentExpression.size() - 1);
  
   currentExpression.add(-operands[current]);
   findExpressions( expressions, currentExpression, sum - currentExpression.get(currentExpression.size() - 1), operands, current + 1);
   currentExpression.remove(currentExpression.size() - 1);
  
  
   //System.out.println(currentExpression);
   int last = currentExpression.get(currentExpression.size() - 1);
   currentExpression.set(currentExpression.size() - 1, last * 10 + operands[current]);
   findExpressions( expressions, currentExpression, sum + last - ((last * 10 + operands[current])), operands, current + 1);
  }
  
  
  
  public static void main(String[] args){
  
      ExpressionFinder expFinder = new ExpressionFinder();
      ArrayList<ArrayList<Integer>> expressions = expFinder.getExpressions(100, new int[] {1,2,3,4,5,6,7,8,9});
  
  
       for(ArrayList<Integer> expression : expressions)
      System.out.println(ExpressionFinder.getReadableExpression(expression));
       }
     }
  

Answer 1

这里有一个更有趣的解决方案来解决这个问题。您可以在三元基中使用加法。为什么是三元？因为你有3个操作:+、-、concat

void ternaryIncrement(int n) {
    int[] a = new int[n - 1];
    for(int i = 0; i < Math.pow(3, n - 1) - 1; i++) {
        a[0]++;
        for(int j = 0; j < n - 1; j++) {
            if(a[j] > 2) {
                a[j] = 0;
                a[j + 1]++;
            }
        }
        // Build your expression base on array
        System.out.println(Arrays.toString(a));
    }
}

对于输入n = 3，您将得到以下输出:

[1, 0]
[2, 0]
[0, 1]
[1, 1]
[2, 1]
[0, 2]
[1, 2]
[2, 2]

请注意，对于 n 个数字，每个数字之间都会有一个运算，因此是 n - 1 个运算。所以你会相应地进行操作。例如，如果为 0，则进行连接；如果为 1，则进行加法；如果为 2，则进行减法。