Cfrgtkky

You could also use recursion here. Just remember your current integer, your max integer, your current sum and some kind of history of operations (could also be your final sequence).
In every level you proceed the path in two dirdctions: adding to your sum and substracting from it.

I did a quick implementation in Python, but it should be easy to transfer this to Java or whatever you are using.

def zero_sum(curr, n, seq, sum):

    if curr == n and sum == 0:

        print(seq)

    elif curr < n:

        zero_sum(curr + 1, n, seq + " - " + str(curr + 1), sum - (curr + 1))

        zero_sum(curr + 1, n, seq + " + " + str(curr + 1), sum + (curr + 1))



zero_sum(1, 7, "1", 1)

Hopefully you get the idea.

The first step is to turn the problem into an entirely regularly formed problem:

 n

 ∑  ±i = -1

i=2



n-2

 ∑  ±(i+2) = -1

i=0

The term 1 at the start has no prefix +/-. And the walking index better runs from 0 when using a Java array.

So one has n-1 coefficients -1 or +1 for the possible values.

A brute force approach would be to start with the highest values, i = n-2.

The upper/lower bounds for j = 0, ..., i would be ± (i + 1) * (2 + i + 2) / 2, so one can cut the evaluation there - when the till then calculated sum can no longer reach -1.

To represent the coefficients, one could make a new int[n - 1] or simply a new BitSet(n-1).

public void solve(int n) {

    int i = n-2;

    int sumDone = 0;

    BigSet negates = new BitSet(n - 1);

    solveRecursively(i, sumDone, negates);

}



private void solveRecursively(int i, int SumDone, BitSet negates) {

    if (i < 0) {

        if (sumDone == -1) {

            System.out.println("Found: " + negates);

        }

        return;

    }

    ...

}

The interesting, actual (home) work I leave to you. (With BitSet better i = n, ... , 2 by -1 seems simpler though.)

If I were you I would go for a graph implementation, and DFS algorithm. Imagine you have N nodes that are representing your numbers. Each number is connected to another via an "add" edge, or a "subtract" edge. So you have a fully connected graph. You can start from a node and compute all dfs paths that lead to zero.

For more information about DFS algorithm, you can see the wikipage.

Edit: In order to clarify my solution, the graph you will end up having will be a multigraph, which means that it has more than one edge between nodes. DFS in a multigraph is slightly more complicated, but it is not that hard.

The question here is how much efficiency matters. If you're content to do a brute-force approach, a regression method like the one indicated by holidayfun is a fine way to go, though this will become unwieldy as n gets large.

If performance speed matters, it may be worth doing a bit of math first. The easiest and most rewarding check is whether such a sum is even possible: since the sum of the first n natural numbers is n(n+1)/2, and since you want to divide this into two groups (a "positive" group and a "negative" group) of equal size, you must have that n(n+1)/4 is an integer. Therefore if neither n nor n+1 is divisible by four, stop. You cannot find such a sequence that adds to zero.

This and a few other math tricks might speed up your application significantly, if speed is of the essence. For instance, finding one solution will often help you find others, for large n. For instance, if n=11, then {-11, -10, -7, -5} is one solution. But we could swap the -5 for any combination that adds to 5 that isn't in our set. Thus {-11, -10, -7, -3, -2} is also a solution, and similarly for -7, giving {-11, -10, -5, -4, -3} as a solution (we are not allowed to use -1 because the 1 must be positive). We could continue replacing the -10, the -11, and their components similarly to pick up six more solutions.

This is probably how I'd approach this problem. Use a greedy algorithm to find the "largest" solution (the solution using the largest possible numbers), then keep splitting the components of that solution into successively smaller solutions. It is again fundamentally a recursion problem, but one whose running time decreases with the size of the component under consideration and which at each step generates another solution if a "smaller" solution exists. That being said, if you want every solution then you still have to check non-greedy combinations of your split (otherwise you'd miss solutions like {-7, -4, -3} in your n=7 example). If you only wanted a lot of solutions it would definitely be faster; but to get all of them it may be no better than a brute-force approach.

I would suggest a straight forward solution because as you mentioned you are dealing with consecutive integer from 1 to N which are fixed. The only things that vary are the operators in between.

Let's look at your example before we implement a general solution:

For n = 7 you need somehow to produce all possible combinations:

1+2+3+4+5+6+7

1+2+3+4+5+6-7

1+2+3+4+5-6+7

1+2+3+4+5-6-7

...

1-2-3-4-5-6+7

1-2-3-4-5-6-7

If we remove the numbers from above strings/expressions then we'll have:

++++++

+++++-

++++-+

++++--

...

----+-

-----+

------

Which reminds on binary numbers; if we interpret + as 0 and - as 1 the above can be mapped to the binary numbers from 000000 to 111111.

For an input n you'll have n-1 operators inbetween, which means the count of all possible combinations will be 2^n-1.

Putting all the above together something like below can be used to print those which sums are zero:

public static void main(String args) throws IOException{

    permute(7);

}

public static void permute(int n){

    int combinations = (int)Math.pow(2, n-1);

    for(int i = 0; i < combinations; i++){

        String operators =String.format("%"+(n-1)+"s", Integer.toBinaryString(i)).replace(' ', '0');



        int totalSum = 1;

        StringBuilder sb = new StringBuilder();



        for(int x = 0; x< operators.length(); x++){

            sb.append(x+1);

            if(operators.charAt(x)=='0'){

                sb.append("+");

                totalSum = totalSum + (x+2);

            }

            else{

                sb.append("-");

                totalSum = totalSum-(x+2);

            }                

        }

        sb.append(n);

        if(totalSum == 0){

            System.out.println(sb.toString() + " = " + totalSum);

        }

    }

}

Note/Example: String.format("%6s", Integer.toBinaryString(13)).replace(' ', '0') will produce a string with length = 6 from the binary representation of 13 with leading zeros, i.e 001101 instead of 1101 so that we get the required length of the operators.

It is a good question, but first you must have to try to solve it and show us what you tried so we can help you in the solution, this way you will improve more effectively.

However, the below code is a solution I have write before years, I think the code need improvement but it will help..

public static void main(String args) {

    String plus = " + ", minus = " - ";

    Set<String> operations = new HashSet<>();

    operations.add("1" + plus);

    operations.add("1" + minus);



    // n >= 3

    int n = 7;



    for (int i = 1; i < n - 1; i++) {

        Set<String> newOperation = new HashSet<>();

        for (String opt : operations) {

            if ((i + 2) == n) {

                newOperation.add(opt + (i + 1) + plus + n);

                newOperation.add(opt + (i + 1) + minus + n);

            } else {

                newOperation.add(opt + (i + 1) + plus);

                newOperation.add(opt + (i + 1) + minus);

            }

        }

        operations.clear();

        operations.addAll(newOperation);

    }

    evalOperations(operations);

}



private static void evalOperations(Set<String> operations) {



    // from JDK1.6, you can use the built-in Javascript engine.

    ScriptEngineManager mgr = new ScriptEngineManager();

    ScriptEngine engine = mgr.getEngineByName("JavaScript");

    try {

        for (String opt : operations) {

            if ((int) engine.eval(opt) == 0) {

                System.out.println(opt + " = 0");

            }

        }

    } catch (ScriptException e) {

        e.printStackTrace();

    }

} 

First, the question is the special case of sum to N.
Second, sum a list to N, could be devided to the first element plus sublist and minus sublist.
Third, if there are only one element in the list, check if n equals the element.
Fourth, make recursion.

Here's the scala implementation, try finishing your java version:

def nSum(nums: List[Int], n: Int, seq: String, res: ListBuffer[String]): Unit =

  nums match {

    case Nil => if (n == 0) res.append(seq)

    case head :: tail => {

      nSum(tail, n - head, seq + s" + $head", res)

      nSum(tail, n + head, seq + s" - $head", res)

    }

  }



def zeroSum(nums: List[Int]): List[String] = {

  val res = ListBuffer[String]()

  nSum(nums.tail, -nums.head, s"${nums.head}", res)

  res.map(_ + " = 0").toList

}



val expected = List(

  "1 + 2 - 3 + 4 - 5 - 6 + 7 = 0",

  "1 + 2 - 3 - 4 + 5 + 6 - 7 = 0",

  "1 - 2 + 3 + 4 - 5 + 6 - 7 = 0",

  "1 - 2 - 3 - 4 - 5 + 6 + 7 = 0")



assert(expected == zeroSum((1 to 7).toList))