Поиск всех возможных комбинаций положительных и отрицательных чисел, равных данной сумме

Question

Как бы вы go, если вы хотите увидеть, каким образом вы можете комбинировать числа от 1 до N таким образом, чтобы при использовании сложения или вычитания вы получали комбинации, равные заданному целевому числу.

Что касается этой топи c Находя все возможные комбинации чисел для достижения заданной суммы , я не смог изменить ее так, чтобы я мог достичь своего результата, поэтому я решил спросить вместо этого.

Пример: (допустим, 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

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 возвращает количество решений, найденных поддеревом

Answer 2

Итеративно, сколько способов достичь цели.

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;
    }
}

Answer 3

Насколько я знаю, и если я понял вопрос, вам нужно for l oop, поскольку, если у вас есть число n, существуют бесконечные комбинации чисел, которые добавляются или вычитаются равными n, поэтому вам нужен номер, который при достижении остановит процесс. Если вам нужно несколько номеров (например, 3 + 10 + 1 = 14), вам нужно больше петель. Это мой путь к go:

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

Надеюсь, это поможет.