找出所有可能组合的正负数，使其总和等于给定值

Question

如果您想知道如何以多少种方法组合从1到N的数字，并通过加或减运算得出等于给定目标数字的组合，该怎么做？

关于这个话题，我无法修改找到达到给定总和的所有可能组合的内容，所以我决定提问。

例如：（假设N = 8。如果我从1到N创建以下数组，我应该如何解决？不要重复使用每个数字。）

arr = [1, 2, 3, 4, 5, 6, 7, 8] sum = 0;

结果：

+1 +2 +3 +4 -5 -6 -7 +8 +1 +2 +3 -4 +5 -6 +7 -8 +1 +2 -3 +4 +5 +6 -7 -8 +1 +2 -3 -4 -5 -6 +7 +8 +1 -2 +3 -4 -5 +6 -7 +8 +1 -2 -3 +4 +5 -6 -7 +8 +1 -2 -3 +4 -5 +6 +7 -8 -1 +2 +3 -4 +5 -6 -7 +8 -1 +2 +3 -4 -5 +6 +7 -8 -1 +2 -3 +4 +5 -6 +7 -8 -1 -2 +3 +4 +5 +6 -7 -8 -1 -2 +3 -4 -5 -6 +7 +8 -1 -2 -3 +4 -5 +6 -7 +8 -1 -2 -3 -4 +5 +6 +7 -8 总解决方案：14

- Knightwalker

---

你能澄清一下你提供的链接中给出的C#答案有什么“不正确”的地方吗？ - Luuk

为什么 +1 -1 +2 -2 +3 -3 +4 -4 可以是一种解决方案，而 +5 -5 +6 -6 +7 -7 +8 -8 却不在你的可能解决方案列表中，这也不是很清楚。 - Luuk

你需要将问题的所有规则都写下来。根据你的规则，我可以随意使用任何数字，从而产生无限数量或组合。 - Carlos Garcia

@CarlosGarcia 我明白了，抱歉。我现在已经重新表达了问题，希望更加清晰易懂。 - Knightwalker

@CarlosGarcia 哇，谢谢你指出来。看起来我把“+1 -1 +2 -2 +3 -3 +4 -4”这个东西放错了，因为我在测试一些东西。规则是我不想重复使用每个数字。已经编辑了问题。 - Knightwalker

Answer 1

以下是一个递归函数，将打印所有有效的组合和无效的组合。

代码（在此测试：这里，或简化版本 这里）：

// This code can be improved a lot, but i wrote it in the way that i believe it is easier to read and understand what it does.

using System;

namespace algorithm_simple_csharp
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Working on it!");

            int[] allNumbers = new int[] {1,2,3,4};
            int desiredSum = 0;

            // We will create two trees, one with a positive first number, and the other one with a negative one

            // Positive tree
            int initIndex = 0;
            OperationTreeNode firstPositiveNode = new OperationTreeNode
            {
                parentNode = null,
                currentNumber = allNumbers[initIndex],
                accumulativeSum = allNumbers[initIndex],
                operation = "+"
            };

            int totalSolutionsPositiveFirst = ApplyNumber(firstPositiveNode, allNumbers, initIndex + 1, desiredSum);

            // Negative tree
            OperationTreeNode firstNegativeNode = new OperationTreeNode
            {
                parentNode = null,
                currentNumber = -allNumbers[initIndex],
                accumulativeSum = -allNumbers[initIndex],
                operation = "-"
            };

            int totalSolutionsNegativeFirst = ApplyNumber(firstNegativeNode, allNumbers, initIndex + 1, desiredSum);

            // Print all solutions found with both trees
            Console.WriteLine("Total soltions: " + (totalSolutionsPositiveFirst + totalSolutionsNegativeFirst));
        }


        // This function will take care of the next number we should apply: allNumbers[index]
        // If there are still numbers to apply, It will create two nodes, one for + allNumbers[index] and one for - allNumbers[index]
        static int ApplyNumber(OperationTreeNode currentNode, int[] allNumbers, int index, int desiredSum)
        {

            // The base case, There are no more numbers to cover.
            // In that case we evaluate if the last node is equal to desiredSum or not
            if(index > allNumbers.GetUpperBound(0))
            {
                if(currentNode.accumulativeSum == desiredSum)
                {
                    Console.WriteLine(currentNode.BranchToString() + " = " + currentNode.accumulativeSum + "  <---   THIS ONE");
                    return 1;
                }

                Console.WriteLine(currentNode.BranchToString() + " = " + currentNode.accumulativeSum);
                return 0;
            }

            // If it is not the last node, then we create two child nodes of the current node.
            // First we evaluate what happens if we apply a + to the next number...
            OperationTreeNode plusNode = new OperationTreeNode
            {
                parentNode = currentNode,
                currentNumber = allNumbers[index],
                accumulativeSum = currentNode.accumulativeSum + allNumbers[index],
                operation = "+"
            };
            int totalSolutionsWithPlus = ApplyNumber(plusNode, allNumbers, index +1, desiredSum);

            // Now we evaluate what happens if we apply a - to the next number...
            OperationTreeNode minusNode = new OperationTreeNode
            {
                parentNode = currentNode,
                currentNumber = allNumbers[index],
                accumulativeSum = currentNode.accumulativeSum - allNumbers[index],
                operation = "-"
            };
            int totalSolutionsWithMinus = ApplyNumber(minusNode, allNumbers, index +1, desiredSum);

            // The total number of solutions we found is the sum of the solutions of both sub-trees
            return totalSolutionsWithPlus + totalSolutionsWithMinus;
        }

    }


    public class OperationTreeNode
    {
        public int accumulativeSum = 0;
        public OperationTreeNode parentNode = null;
        public int currentNumber = 0;
        public string operation;

        public string BranchToString()
        {
            if(parentNode == null)
            {
                return $"{this.currentNumber} ";
            }

            return $"{parentNode.BranchToString()} {this.operation} {this.currentNumber} ";
        }
    }
}

控制台输出

Working on it!
1  + 2  + 3  + 4  = 10
1  + 2  + 3  - 4  = 2
1  + 2  - 3  + 4  = 4
1  + 2  - 3  - 4  = -4
1  - 2  + 3  + 4  = 6
1  - 2  + 3  - 4  = -2
1  - 2  - 3  + 4  = 0  <---   THIS ONE
1  - 2  - 3  - 4  = -8
-1  + 2  + 3  + 4  = 8
-1  + 2  + 3  - 4  = 0  <---   THIS ONE
-1  + 2  - 3  + 4  = 2
-1  + 2  - 3  - 4  = -6
-1  - 2  + 3  + 4  = 4
-1  - 2  + 3  - 4  = -4
-1  - 2  - 3  + 4  = -2
-1  - 2  - 3  - 4  = -10
Total soltions: 2

它是如何工作的？

它创建一棵树。每个树节点都是类型为OperationTreeNode的对象，表示数字及其操作。例如：+1和-1是两个OperationTreeNode。

当您到达最后一个数字时，ApplyNumber将评估该节点是否等于desiredSum。

ApplyNumber返回子树找到多少解决方案。

- Carlos Garcia

---

谢谢您的回答，但是看起来我可能错了，我无法很好地理解我的问题，因为您的解决方案肯定是正确的，但是根据示例它并不能解决我的问题。如果我运行您提供的代码，例如arr = [1, 2, 3, 4, 5, 6, 7, 8]，targetSum = 0; 我将得到7个解决方案，而不是14个。您的代码是否检查数组的第一个索引处是否有+1或-1？（提前感谢您） - Knightwalker

@Knightwalker 不会的，这里执行了两个树，一个是正数第一个索引，另一个是负数的：dotnetfiddle.net/O4IeRd。你也可以写出更好的代码。例如，这个代码已经更短了，只打印成功的情况：https://dotnetfiddle.net/MP4U0f。 - Carlos Garcia

我真的非常感激你的帮助和解释！你是正确的。我希望有一天能够达到你的水平。对于像我这样的初学者来说，这可能看起来像一个基本的递归函数，但却是地狱，哈哈。 - Knightwalker

@Knightwalker 你会做得非常好！ :) 如果我的代码难以理解，这是相同的算法，但更简单（不使用对象）：https://dotnetfiddle.net/BnBIo6 - Carlos Garcia

控制台输出：-1 + 2 + 3 + 4 = 10？ - P_P

Answer 2

据我所知，如果我理解问题正确的话，你需要一个 for 循环，因为如果你有一个数字 n，那么有无限组数字相加或相减等于 n，所以你需要一个数字，如果达到了这个数字，就会停止这个过程。 如果你需要多个数字（例如 3+10+1=14），你需要更多的循环。 这是我的方法：

int l = 50;//my limit
int n = 14;//my number
for(int i = 0; i < l; i++) 
        {
           for(int j = 0; j < l; j++) 
           {
                if ( i + j == n ) 
                {
                //Do whatever you want
                        Console.WriteLine("{0} = {1} + {2}", n, i, j);
                }
                if ( i - j == n ) 
                {
                //Do whatever you want
                       Console.WriteLine("{0} = {1} - {2}", n, i, j);
                }
         }
      }//Repeat for negative numbers

希望这能有所帮助。

- Adryzz

Answer 3

迭代，达到目标的方式有多少种。

using System;
class Program
{
    static void Main()
    {
        Console.WriteLine(C(0));
        int[] a = { 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144 };
        Console.Write(C(0, a)); Console.Read();
    }

    static int C(int t)  // ±1 ± 2 ± 3 ± 4 == 0
    {
        int c = 0, s = 0;
        for (int n = 0; n < 16; n++)
        {
            if ((n & 1) == 0) s -= 1; else s += 1;
            if ((n & 2) == 0) s -= 2; else s += 2;
            if ((n & 4) == 0) s -= 3; else s += 3;
            if ((n & 8) == 0) s -= 4; else s += 4;
            if (s == t) c++; s = 0;
        } return c;
    }

    static int C(int t, int[] a)
    {
        int c = 0, s = 0, i, j = a.Length, n, m = 1 << j;
        for (n = 0; n < m; n++)
        {
            for (i = 0; i < j; i++)
                if ((n & 1 << i) == 0) s -= a[i]; else s += a[i];
            if (s == t) c++; s = 0;
        } return c;
    }
}

- P_P