Finding all possible combinations of positive and negative numbers that equal a given sum

Question

How would you go if you want to see in how many ways you can combine the numbers from 1 to N in such a way that by using addition or subtraction you will end up with combinations that equal a given target number.

In regards to this topic Finding all possible combinations of numbers to reach a given sum, I was unable to modify it in a way that I could achieve my result, so I decided to ask instead.

Example: (Lets say that N = 8. How would I approach to solve this if I create the following array from 1 to N. Don't use each number more than once.)

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

Result:

• +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
• Total Solutions: 14

Answer 1

Here a recursive function that will print all the combinations that worked, and the ones that did not work.

The code (test it here, or a simpler version here):

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

The output in the console

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

How it works?

It creates a tree. Each node of the tree is an object of type OperationTreeNode that represents a number and its operation. for example: +1 and -1 are two OperationTreeNode

when you reached the last number, ApplyNumber will evaluate if the node is equal to desiredSum.

ApplyNumber returns how many solutions that subtree found

Answer 2

As far as i know, and if i've understood the question, you need a for loop since if you have a number n, there are infinite combinations of numbers that added or subtracted equals n, so you need a number that, if reached will stop the process. If you need multiple number (e.g. 3+10+1=14) you need more loops. This would be my way to 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

Hope this will help.

Answer 3

Iterative, how many ways to reach a target.

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