找到数组的所有可能数字组合以达到给定的总和

Question

我们得到了一个包含 N 个数字的数组和一个目标值 k。我们需要通过插入运算符（+、- 和 *）来找到所有可能的方式来形成表达式，以使表达式的计算结果为值 k。
例如：

输入：数组 = {3,4,3}，k = 15
输出：3*4+3, 3+4*3

我无法针对此问题开发递归解决方案。仅使用 '+' 和 '-' 运算符，这会更容易，但由于 '*' 运算符，使用递归方法变得困难，因为我们还需要关心运算符的优先级。你能帮我找到一个合适的方法来解决这个问题吗？

Answer 1

我花了一些时间来编写这个代码。所以这基本上是蛮力。我使用给定的运算符递归（回溯）生成所有可能的表达式，然后对它们进行求值。请注意，这些只是中缀表达式。

现在这是一个非常慢的解决方案。这里有几个优化可以做。

vector<string> allCombinations(vector<int> &arr, int k)
{
    int n = (int)arr.size();
    string operators = "+-*";
    vector<string> ans;
    // To check precedence of operators
    auto prec = [&](char op) -> int
    {
        if (op == '*' or op == '/') return 2;
        if (op == '+' or op == '-') return 1;
        return -1;
    };
    // For infix evaluation (kindof a helper function)
    auto compute = [&](int v1, char op, int v2) -> int
    {
        if (op == '+') return v1 + v2;
        if (op == '-') return v1 - v2;
        if (op == '*') return v1 * v2;
        if (op == '/') return v1 / v2;
        assert(false);
        return INT_MAX;
    };
    // Main infix evaluation function
    auto evaluate = [&](string s) -> int
    {
        int len = (int)s.size();
        // vector is being used as a STACK
        vector<int> val;
        vector<char> ops;
        for (int i = 0; i < len; i++)
        {
            char curr = s[i];
            if (curr == ' ') continue;
            if (isdigit(curr))
            {
                int v = 0;
                while (i < len and isdigit(s[i])) v = 10 * v + (s[i++] - '0');
                val.push_back(v);
                i--;
            }
            else
            {
                while (!ops.empty() and prec(curr) <= prec(ops.back()))
                {
                    int v1 = val.back();
                    val.pop_back();
                    int v2 = val.back();
                    val.pop_back();
                    char op = ops.back();
                    ops.pop_back();
                    val.push_back(compute(v2, op, v1));
                }
                ops.push_back(curr);
            }
        }
        while (!ops.empty())
        {
            int v1 = val.back();
            val.pop_back();
            int v2 = val.back();
            val.pop_back();
            char op = ops.back();
            ops.pop_back();
            val.push_back(compute(v2, op, v1));
        }
        return val.back();
    };
    // Generates all expression possible
    function<void(int, string&)> generate = [&](int i, string &s) -> void
    {
        s += to_string(arr[i]);
        if (i == n - 1)
        {
            if (evaluate(s) == k) ans.push_back(s);
            // Backtrack
            s.pop_back();
            return;
        }
        for (char &ops : operators) 
        {
            s.push_back(ops);
            generate(i + 1, s);
            // Backtrack
            s.pop_back();
        }
        // Backtrack
        s.pop_back();
    };
    string s;
    // Try all combinations
    sort(arr.begin(), arr.end());
    do
    {
        generate(0, s);
    } while (next_permutation(arr.begin(), arr.end()));
    return ans;
}

Answer 2

查找运算符的所有组合非常简单。如果您将每个运算符表示为 base-3 中 zero-prefixed 数字的数字，那么您可以创建一个函数，从整数中呈现该 base-3 数字，但使用 {'+','-',' *'} 而不是 {'0','1','2'} 作为数字。

private static final char[] CHARS = "+-*".toCharArray();
private char[] generateOperators(int i, int length){
    char[] ops=new char[length];
    for (int x=0; x<length; x++) ops[x]=CHARS[0];
    for (int x=0; x<length; x++) {
        ops[length-1-x]=CHARS[i % CHARS.length];
        i /= CHARS.length;
    }
    return ops;
}

您可以不回溯地从左到右累计您的总数。保留一个总数和一个单独的累加器。任何时候你的下一个操作数是“+”或“-”，将你的累计值推到总数是安全的。如果是'*'，那么你知道当前操作数正在参与下一次累加。在此函数中，我基本上将每个运行的相乘操作数视为一个簇，甚至将单个值视为一个簇，并在到达簇末尾时将累加值推入总数。

public int evaluate(int[] operands, char[] operators) {
    int sum=0;
    int multiplier=1;
    for (int i=0; i<operators.length; i++) {
        int operand=operands[i];
        multiplier*=operand;
        if (operators[i]!='*') {
            sum+=multiplier;
            multiplier=operators[i]=='-' ? -1 : 1;
        }
    }
    if (operators[operators.length-1]=='*') {
        multiplier*=operands[operands.length-1];
    } else {
        multiplier=(operators[operators.length-1]=='-' ? -1 : 1) * operands[operands.length-1];
    }
    sum+=multiplier;
    return sum;
}

找到数组的所有可能数字组合以达到给定的总和

Finding all possible combinations of numbers of an array to reach a given sum

algorithm

recursion