c# - 从数字数组中找出所有的加减法组合

Question

我需要创建一个函数来接收一个数字数组和一个目标数字，并返回您可以通过多少种不同的方式来加减这些数字以获得目标数字。

即。

值 = 2、4、6、8 目标 = 12

2 + 4 + 6 = 12，

4 + 8 = 12，

6 + 8 - 2 = 12,

2 - 4 + 6 + 8 = 12,

返回 4

这是我到目前为止的结果，但它只计算加法问题。

private void RecursiveSolve(int goal, int currentSum, List<int> included, List<int> notIncluded, int startIndex) 
{
    for (int index = startIndex; index < notIncluded.Count; index++) 
    {
        int nextValue = notIncluded[index];
        if (currentSum + nextValue == goal)
        {
            List<int> newResult = new List<int>(included);
            newResult.Add(nextValue);
            mResults.Add(newResult);
        }
        else if (currentSum - nextValue == goal)
        {
            List<int> newResult = new List<int>(included);
            newResult.Add(nextValue);
            mResults.Add(newResult);
        }

        if (currentSum - nextValue < goal && currentSum - nextValue > 0 )
        {
            List<int> nextIncluded = new List<int>(included);
            nextIncluded.Add(nextValue);
            List<int> nextNotIncluded = new List<int>(notIncluded);
            nextNotIncluded.Remove(nextValue);
            RecursiveSolve(goal, currentSum - nextValue, nextIncluded, nextNotIncluded, startIndex++);
        }

        if (currentSum + nextValue < goal)
        {
            List<int> nextIncluded = new List<int>(included);
            nextIncluded.Add(nextValue);
            List<int> nextNotIncluded = new List<int>(notIncluded);
            nextNotIncluded.Remove(nextValue);
            RecursiveSolve(goal, currentSum + nextValue, nextIncluded, nextNotIncluded, startIndex++);
        }
    }
}

Answer 1

好吧，简单的方法就是尝试所有的组合。如果有 N 个数字，则有 3^N 种组合。推理是这样的:你对数字求和，但在每个数字前面加上一个系数。如果你的数字是 A1..AN，你添加 N 个系数 (C1..CN) 并求和:

Sum (Ai*Ci)

您的 Cis 可以是 1(意味着您添加数字)、-1(意味着您减去数字)或 0(意味着您忽略数字)。

因此，遍历所有 3^N 个可能的系数分配，计算总和并与您的目标进行比较。

我假设所有数字都不同(如您的示例所示)。如果一个数字可以出现两次，您需要考虑到这一点。