Total of all numbers from 1 to N will always be zeroDoes a finally block always get executed in Java?Create ArrayList from arrayAdd leading zeroes to number in Java?How do I call one constructor from another in Java?Fastest way to determine if an integer's square root is an integerHow can I pad an integer with zeros on the left?Why can't I define a static method in a Java interface?How to get an enum value from a string value in Java?How to nicely format floating numbers to String without unnecessary decimal 0?possible combination in binary counting

Are student evaluations of teaching assistants read by others in the faculty?

Would a high gravity rocky planet be guaranteed to have an atmosphere?

Sort a list by elements of another list

Was Spock the First Vulcan in Starfleet?

What is the best translation for "slot" in the context of multiplayer video games?

What can we do to stop prior company from asking us questions?

How can a function with a hole (removable discontinuity) equal a function with no hole?

I'm in charge of equipment buying but no one's ever happy with what I choose. How to fix this?

How can I get through very long and very dry, but also very useful technical documents when learning a new tool?

Where does the Z80 processor start executing from?

Unreliable Magic - Is it worth it?

How to check is there any negative term in a large list?

Why didn't Theresa May consult with Parliament before negotiating a deal with the EU?

What is paid subscription needed for in Mortal Kombat 11?

Did Dumbledore lie to Harry about how long he had James Potter's invisibility cloak when he was examining it? If so, why?

What is the difference between "behavior" and "behaviour"?

How to run a prison with the smallest amount of guards?

Method to test if a number is a perfect power?

How easy is it to start Magic from scratch?

How does Loki do this?

Escape a backup date in a file name

Risk of infection at the gym?

Closest Prime Number

How do I find the solutions of the following equation?



Total of all numbers from 1 to N will always be zero


Does a finally block always get executed in Java?Create ArrayList from arrayAdd leading zeroes to number in Java?How do I call one constructor from another in Java?Fastest way to determine if an integer's square root is an integerHow can I pad an integer with zeros on the left?Why can't I define a static method in a Java interface?How to get an enum value from a string value in Java?How to nicely format floating numbers to String without unnecessary decimal 0?possible combination in binary counting













4















The problem is I have to print all combinations of a sequence of
numbers from 1 to N that will always result to zero. It is allowed
to insert "+" (for adding) and "-" (for subtracting) between each
numbers so that the result will be zero.



//Output
N = 7

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


So how can I implement this? I am not asking for the actual
codes to do this, just a hint and ideas to solve this will
do. Thank you..










share|improve this question






















  • I suppose that your constraint is that numbers cannot be repeated and always begin with the smallest and finish with the biggest, I would try to find any recursive solution you know that you have to stop when n is equal to N and only print when the result is 0.

    – vmrvictor
    yesterday











  • Can the numbers be repeated? Can you add the minus before the first number?

    – Karol Dowbecki
    yesterday











  • @KarolDowbecki no just conscecutive integer from 1 to N

    – robert
    yesterday











  • @robert If it can't, please update your question to fill in this extra constraint.

    – tryman
    yesterday






  • 1





    @Lino what it was exactly stated is the sum of consecutive integers that will always result to zero. It says that we can either insert + or - between each numbers. So the number 1 will always be positive...

    – robert
    yesterday















4















The problem is I have to print all combinations of a sequence of
numbers from 1 to N that will always result to zero. It is allowed
to insert "+" (for adding) and "-" (for subtracting) between each
numbers so that the result will be zero.



//Output
N = 7

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


So how can I implement this? I am not asking for the actual
codes to do this, just a hint and ideas to solve this will
do. Thank you..










share|improve this question






















  • I suppose that your constraint is that numbers cannot be repeated and always begin with the smallest and finish with the biggest, I would try to find any recursive solution you know that you have to stop when n is equal to N and only print when the result is 0.

    – vmrvictor
    yesterday











  • Can the numbers be repeated? Can you add the minus before the first number?

    – Karol Dowbecki
    yesterday











  • @KarolDowbecki no just conscecutive integer from 1 to N

    – robert
    yesterday











  • @robert If it can't, please update your question to fill in this extra constraint.

    – tryman
    yesterday






  • 1





    @Lino what it was exactly stated is the sum of consecutive integers that will always result to zero. It says that we can either insert + or - between each numbers. So the number 1 will always be positive...

    – robert
    yesterday













4












4








4


1






The problem is I have to print all combinations of a sequence of
numbers from 1 to N that will always result to zero. It is allowed
to insert "+" (for adding) and "-" (for subtracting) between each
numbers so that the result will be zero.



//Output
N = 7

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


So how can I implement this? I am not asking for the actual
codes to do this, just a hint and ideas to solve this will
do. Thank you..










share|improve this question














The problem is I have to print all combinations of a sequence of
numbers from 1 to N that will always result to zero. It is allowed
to insert "+" (for adding) and "-" (for subtracting) between each
numbers so that the result will be zero.



//Output
N = 7

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


So how can I implement this? I am not asking for the actual
codes to do this, just a hint and ideas to solve this will
do. Thank you..







java






share|improve this question













share|improve this question











share|improve this question




share|improve this question










asked yesterday









robertrobert

856




856












  • I suppose that your constraint is that numbers cannot be repeated and always begin with the smallest and finish with the biggest, I would try to find any recursive solution you know that you have to stop when n is equal to N and only print when the result is 0.

    – vmrvictor
    yesterday











  • Can the numbers be repeated? Can you add the minus before the first number?

    – Karol Dowbecki
    yesterday











  • @KarolDowbecki no just conscecutive integer from 1 to N

    – robert
    yesterday











  • @robert If it can't, please update your question to fill in this extra constraint.

    – tryman
    yesterday






  • 1





    @Lino what it was exactly stated is the sum of consecutive integers that will always result to zero. It says that we can either insert + or - between each numbers. So the number 1 will always be positive...

    – robert
    yesterday

















  • I suppose that your constraint is that numbers cannot be repeated and always begin with the smallest and finish with the biggest, I would try to find any recursive solution you know that you have to stop when n is equal to N and only print when the result is 0.

    – vmrvictor
    yesterday











  • Can the numbers be repeated? Can you add the minus before the first number?

    – Karol Dowbecki
    yesterday











  • @KarolDowbecki no just conscecutive integer from 1 to N

    – robert
    yesterday











  • @robert If it can't, please update your question to fill in this extra constraint.

    – tryman
    yesterday






  • 1





    @Lino what it was exactly stated is the sum of consecutive integers that will always result to zero. It says that we can either insert + or - between each numbers. So the number 1 will always be positive...

    – robert
    yesterday
















I suppose that your constraint is that numbers cannot be repeated and always begin with the smallest and finish with the biggest, I would try to find any recursive solution you know that you have to stop when n is equal to N and only print when the result is 0.

– vmrvictor
yesterday





I suppose that your constraint is that numbers cannot be repeated and always begin with the smallest and finish with the biggest, I would try to find any recursive solution you know that you have to stop when n is equal to N and only print when the result is 0.

– vmrvictor
yesterday













Can the numbers be repeated? Can you add the minus before the first number?

– Karol Dowbecki
yesterday





Can the numbers be repeated? Can you add the minus before the first number?

– Karol Dowbecki
yesterday













@KarolDowbecki no just conscecutive integer from 1 to N

– robert
yesterday





@KarolDowbecki no just conscecutive integer from 1 to N

– robert
yesterday













@robert If it can't, please update your question to fill in this extra constraint.

– tryman
yesterday





@robert If it can't, please update your question to fill in this extra constraint.

– tryman
yesterday




1




1





@Lino what it was exactly stated is the sum of consecutive integers that will always result to zero. It says that we can either insert + or - between each numbers. So the number 1 will always be positive...

– robert
yesterday





@Lino what it was exactly stated is the sum of consecutive integers that will always result to zero. It says that we can either insert + or - between each numbers. So the number 1 will always be positive...

– robert
yesterday












7 Answers
7






active

oldest

votes


















10














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.






share|improve this answer










New contributor




holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.















  • 2





    You can not actually return anything using this approach, for eg: output String.

    – roundAbout
    yesterday











  • The OP asked for printing the valid combinations. If it was necessary to return a long string of valid combinations you could return a single valid combination when ending the recursion and the levels above could concatenate the results of the two recursive calls.

    – holidayfun
    yesterday











  • What about using yield seq instead of print(seq) and yield from zero_sum(...) instead of zero_sum(...) to make it more reusable?

    – Solomon Ucko
    yesterday


















4














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.)






share|improve this answer






























    3














    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.






    share|improve this answer

























    • is it possible to just use ordinary manipulations of array?

      – robert
      yesterday











    • @robert You can implement your graph with an Adjacency List. geeksforgeeks.org/graph-and-its-representations

      – Farhood ET
      yesterday











    • @robert I have edited my post.

      – Farhood ET
      yesterday






    • 1





      Is there a little bit more simpler than that? To be honest I don't know anything about a graph in java yet. This problem that I am asking is just included in the recursion section of our java class specifically about permutations, so I am expecting any ideas that relates in implementing permutations and combinations or something like that....

      – robert
      yesterday






    • 1





      @robert check holidayfun's answer.

      – Farhood ET
      yesterday


















    2














    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.






    share|improve this answer






























      1














      Brute force approach:



      var input = 7; // change me

      var s = "1".repeat(input);
      IntStream.rangeClosed(0, Integer.parseInt(s, 2))
      .mapToObj(e ->
      var str = Integer.toBinaryString(e);
      return "0".repeat(input - str.length()) + str; // padding zeros
      )
      .forEach(binStr ->
      var total = 0;
      var plusMinus = binStr.split(""); // splitting binary string to String[]
      var sb = new StringBuilder();
      for(int i = 0; i < plusMinus.length; i++)
      var pm = plusMinus[i].equals("1") ? "+": "-";
      var j = i + 1;
      total = pm.equals("+") ? (total + j): (total - j);
      sb.append(pm).append(j);

      sb.append(" = ").append(total);
      if(total == 0)
      System.out.println(sb.toString());

      );


      The idea is to create binary string starting from 0000000 to 1111111 if the input is 7 where 0,1 represents -,+ and start looping. Now create another loop and apply the +/- operations for 1/0 to check if the total is 0 while creating a string from the operations performed. If the total is 0 then print the string that we got from performing the operations.






      share|improve this answer























      • This approach takes same amount of time as a recursive method in java. STRANGE.

        – roundAbout
        yesterday






      • 1





        @roundAbout But recursion is a cleaner approach.

        – Aniket Sahrawat
        yesterday











      • @roundAbout it does the same amount of work, it's just an iterative implementation of the same algorithm.

        – Baldrickk
        yesterday


















      1














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



      Lets look at your example before we impliment 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.






      share|improve this answer






























        0














        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();







        share|improve this answer
























          Your Answer






          StackExchange.ifUsing("editor", function ()
          StackExchange.using("externalEditor", function ()
          StackExchange.using("snippets", function ()
          StackExchange.snippets.init();
          );
          );
          , "code-snippets");

          StackExchange.ready(function()
          var channelOptions =
          tags: "".split(" "),
          id: "1"
          ;
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function()
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled)
          StackExchange.using("snippets", function()
          createEditor();
          );

          else
          createEditor();

          );

          function createEditor()
          StackExchange.prepareEditor(
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: true,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: 10,
          bindNavPrevention: true,
          postfix: "",
          imageUploader:
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          ,
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          );



          );













          draft saved

          draft discarded


















          StackExchange.ready(
          function ()
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55354283%2ftotal-of-all-numbers-from-1-to-n-will-always-be-zero%23new-answer', 'question_page');

          );

          Post as a guest















          Required, but never shown

























          7 Answers
          7






          active

          oldest

          votes








          7 Answers
          7






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          10














          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.






          share|improve this answer










          New contributor




          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.















          • 2





            You can not actually return anything using this approach, for eg: output String.

            – roundAbout
            yesterday











          • The OP asked for printing the valid combinations. If it was necessary to return a long string of valid combinations you could return a single valid combination when ending the recursion and the levels above could concatenate the results of the two recursive calls.

            – holidayfun
            yesterday











          • What about using yield seq instead of print(seq) and yield from zero_sum(...) instead of zero_sum(...) to make it more reusable?

            – Solomon Ucko
            yesterday















          10














          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.






          share|improve this answer










          New contributor




          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.















          • 2





            You can not actually return anything using this approach, for eg: output String.

            – roundAbout
            yesterday











          • The OP asked for printing the valid combinations. If it was necessary to return a long string of valid combinations you could return a single valid combination when ending the recursion and the levels above could concatenate the results of the two recursive calls.

            – holidayfun
            yesterday











          • What about using yield seq instead of print(seq) and yield from zero_sum(...) instead of zero_sum(...) to make it more reusable?

            – Solomon Ucko
            yesterday













          10












          10








          10







          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.






          share|improve this answer










          New contributor




          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.










          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.







          share|improve this answer










          New contributor




          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.









          share|improve this answer



          share|improve this answer








          edited yesterday





















          New contributor




          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.









          answered yesterday









          holidayfunholidayfun

          1015




          1015




          New contributor




          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.





          New contributor





          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.






          holidayfun is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
          Check out our Code of Conduct.







          • 2





            You can not actually return anything using this approach, for eg: output String.

            – roundAbout
            yesterday











          • The OP asked for printing the valid combinations. If it was necessary to return a long string of valid combinations you could return a single valid combination when ending the recursion and the levels above could concatenate the results of the two recursive calls.

            – holidayfun
            yesterday











          • What about using yield seq instead of print(seq) and yield from zero_sum(...) instead of zero_sum(...) to make it more reusable?

            – Solomon Ucko
            yesterday












          • 2





            You can not actually return anything using this approach, for eg: output String.

            – roundAbout
            yesterday











          • The OP asked for printing the valid combinations. If it was necessary to return a long string of valid combinations you could return a single valid combination when ending the recursion and the levels above could concatenate the results of the two recursive calls.

            – holidayfun
            yesterday











          • What about using yield seq instead of print(seq) and yield from zero_sum(...) instead of zero_sum(...) to make it more reusable?

            – Solomon Ucko
            yesterday







          2




          2





          You can not actually return anything using this approach, for eg: output String.

          – roundAbout
          yesterday





          You can not actually return anything using this approach, for eg: output String.

          – roundAbout
          yesterday













          The OP asked for printing the valid combinations. If it was necessary to return a long string of valid combinations you could return a single valid combination when ending the recursion and the levels above could concatenate the results of the two recursive calls.

          – holidayfun
          yesterday





          The OP asked for printing the valid combinations. If it was necessary to return a long string of valid combinations you could return a single valid combination when ending the recursion and the levels above could concatenate the results of the two recursive calls.

          – holidayfun
          yesterday













          What about using yield seq instead of print(seq) and yield from zero_sum(...) instead of zero_sum(...) to make it more reusable?

          – Solomon Ucko
          yesterday





          What about using yield seq instead of print(seq) and yield from zero_sum(...) instead of zero_sum(...) to make it more reusable?

          – Solomon Ucko
          yesterday













          4














          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.)






          share|improve this answer



























            4














            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.)






            share|improve this answer

























              4












              4








              4







              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.)






              share|improve this answer













              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.)







              share|improve this answer












              share|improve this answer



              share|improve this answer










              answered yesterday









              Joop EggenJoop Eggen

              78.6k755105




              78.6k755105





















                  3














                  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.






                  share|improve this answer

























                  • is it possible to just use ordinary manipulations of array?

                    – robert
                    yesterday











                  • @robert You can implement your graph with an Adjacency List. geeksforgeeks.org/graph-and-its-representations

                    – Farhood ET
                    yesterday











                  • @robert I have edited my post.

                    – Farhood ET
                    yesterday






                  • 1





                    Is there a little bit more simpler than that? To be honest I don't know anything about a graph in java yet. This problem that I am asking is just included in the recursion section of our java class specifically about permutations, so I am expecting any ideas that relates in implementing permutations and combinations or something like that....

                    – robert
                    yesterday






                  • 1





                    @robert check holidayfun's answer.

                    – Farhood ET
                    yesterday















                  3














                  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.






                  share|improve this answer

























                  • is it possible to just use ordinary manipulations of array?

                    – robert
                    yesterday











                  • @robert You can implement your graph with an Adjacency List. geeksforgeeks.org/graph-and-its-representations

                    – Farhood ET
                    yesterday











                  • @robert I have edited my post.

                    – Farhood ET
                    yesterday






                  • 1





                    Is there a little bit more simpler than that? To be honest I don't know anything about a graph in java yet. This problem that I am asking is just included in the recursion section of our java class specifically about permutations, so I am expecting any ideas that relates in implementing permutations and combinations or something like that....

                    – robert
                    yesterday






                  • 1





                    @robert check holidayfun's answer.

                    – Farhood ET
                    yesterday













                  3












                  3








                  3







                  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.






                  share|improve this answer















                  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.







                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited yesterday

























                  answered yesterday









                  Farhood ETFarhood ET

                  19011




                  19011












                  • is it possible to just use ordinary manipulations of array?

                    – robert
                    yesterday











                  • @robert You can implement your graph with an Adjacency List. geeksforgeeks.org/graph-and-its-representations

                    – Farhood ET
                    yesterday











                  • @robert I have edited my post.

                    – Farhood ET
                    yesterday






                  • 1





                    Is there a little bit more simpler than that? To be honest I don't know anything about a graph in java yet. This problem that I am asking is just included in the recursion section of our java class specifically about permutations, so I am expecting any ideas that relates in implementing permutations and combinations or something like that....

                    – robert
                    yesterday






                  • 1





                    @robert check holidayfun's answer.

                    – Farhood ET
                    yesterday

















                  • is it possible to just use ordinary manipulations of array?

                    – robert
                    yesterday











                  • @robert You can implement your graph with an Adjacency List. geeksforgeeks.org/graph-and-its-representations

                    – Farhood ET
                    yesterday











                  • @robert I have edited my post.

                    – Farhood ET
                    yesterday






                  • 1





                    Is there a little bit more simpler than that? To be honest I don't know anything about a graph in java yet. This problem that I am asking is just included in the recursion section of our java class specifically about permutations, so I am expecting any ideas that relates in implementing permutations and combinations or something like that....

                    – robert
                    yesterday






                  • 1





                    @robert check holidayfun's answer.

                    – Farhood ET
                    yesterday
















                  is it possible to just use ordinary manipulations of array?

                  – robert
                  yesterday





                  is it possible to just use ordinary manipulations of array?

                  – robert
                  yesterday













                  @robert You can implement your graph with an Adjacency List. geeksforgeeks.org/graph-and-its-representations

                  – Farhood ET
                  yesterday





                  @robert You can implement your graph with an Adjacency List. geeksforgeeks.org/graph-and-its-representations

                  – Farhood ET
                  yesterday













                  @robert I have edited my post.

                  – Farhood ET
                  yesterday





                  @robert I have edited my post.

                  – Farhood ET
                  yesterday




                  1




                  1





                  Is there a little bit more simpler than that? To be honest I don't know anything about a graph in java yet. This problem that I am asking is just included in the recursion section of our java class specifically about permutations, so I am expecting any ideas that relates in implementing permutations and combinations or something like that....

                  – robert
                  yesterday





                  Is there a little bit more simpler than that? To be honest I don't know anything about a graph in java yet. This problem that I am asking is just included in the recursion section of our java class specifically about permutations, so I am expecting any ideas that relates in implementing permutations and combinations or something like that....

                  – robert
                  yesterday




                  1




                  1





                  @robert check holidayfun's answer.

                  – Farhood ET
                  yesterday





                  @robert check holidayfun's answer.

                  – Farhood ET
                  yesterday











                  2














                  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.






                  share|improve this answer



























                    2














                    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.






                    share|improve this answer

























                      2












                      2








                      2







                      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.






                      share|improve this answer













                      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.







                      share|improve this answer












                      share|improve this answer



                      share|improve this answer










                      answered yesterday









                      GalendoGalendo

                      1285




                      1285





















                          1














                          Brute force approach:



                          var input = 7; // change me

                          var s = "1".repeat(input);
                          IntStream.rangeClosed(0, Integer.parseInt(s, 2))
                          .mapToObj(e ->
                          var str = Integer.toBinaryString(e);
                          return "0".repeat(input - str.length()) + str; // padding zeros
                          )
                          .forEach(binStr ->
                          var total = 0;
                          var plusMinus = binStr.split(""); // splitting binary string to String[]
                          var sb = new StringBuilder();
                          for(int i = 0; i < plusMinus.length; i++)
                          var pm = plusMinus[i].equals("1") ? "+": "-";
                          var j = i + 1;
                          total = pm.equals("+") ? (total + j): (total - j);
                          sb.append(pm).append(j);

                          sb.append(" = ").append(total);
                          if(total == 0)
                          System.out.println(sb.toString());

                          );


                          The idea is to create binary string starting from 0000000 to 1111111 if the input is 7 where 0,1 represents -,+ and start looping. Now create another loop and apply the +/- operations for 1/0 to check if the total is 0 while creating a string from the operations performed. If the total is 0 then print the string that we got from performing the operations.






                          share|improve this answer























                          • This approach takes same amount of time as a recursive method in java. STRANGE.

                            – roundAbout
                            yesterday






                          • 1





                            @roundAbout But recursion is a cleaner approach.

                            – Aniket Sahrawat
                            yesterday











                          • @roundAbout it does the same amount of work, it's just an iterative implementation of the same algorithm.

                            – Baldrickk
                            yesterday















                          1














                          Brute force approach:



                          var input = 7; // change me

                          var s = "1".repeat(input);
                          IntStream.rangeClosed(0, Integer.parseInt(s, 2))
                          .mapToObj(e ->
                          var str = Integer.toBinaryString(e);
                          return "0".repeat(input - str.length()) + str; // padding zeros
                          )
                          .forEach(binStr ->
                          var total = 0;
                          var plusMinus = binStr.split(""); // splitting binary string to String[]
                          var sb = new StringBuilder();
                          for(int i = 0; i < plusMinus.length; i++)
                          var pm = plusMinus[i].equals("1") ? "+": "-";
                          var j = i + 1;
                          total = pm.equals("+") ? (total + j): (total - j);
                          sb.append(pm).append(j);

                          sb.append(" = ").append(total);
                          if(total == 0)
                          System.out.println(sb.toString());

                          );


                          The idea is to create binary string starting from 0000000 to 1111111 if the input is 7 where 0,1 represents -,+ and start looping. Now create another loop and apply the +/- operations for 1/0 to check if the total is 0 while creating a string from the operations performed. If the total is 0 then print the string that we got from performing the operations.






                          share|improve this answer























                          • This approach takes same amount of time as a recursive method in java. STRANGE.

                            – roundAbout
                            yesterday






                          • 1





                            @roundAbout But recursion is a cleaner approach.

                            – Aniket Sahrawat
                            yesterday











                          • @roundAbout it does the same amount of work, it's just an iterative implementation of the same algorithm.

                            – Baldrickk
                            yesterday













                          1












                          1








                          1







                          Brute force approach:



                          var input = 7; // change me

                          var s = "1".repeat(input);
                          IntStream.rangeClosed(0, Integer.parseInt(s, 2))
                          .mapToObj(e ->
                          var str = Integer.toBinaryString(e);
                          return "0".repeat(input - str.length()) + str; // padding zeros
                          )
                          .forEach(binStr ->
                          var total = 0;
                          var plusMinus = binStr.split(""); // splitting binary string to String[]
                          var sb = new StringBuilder();
                          for(int i = 0; i < plusMinus.length; i++)
                          var pm = plusMinus[i].equals("1") ? "+": "-";
                          var j = i + 1;
                          total = pm.equals("+") ? (total + j): (total - j);
                          sb.append(pm).append(j);

                          sb.append(" = ").append(total);
                          if(total == 0)
                          System.out.println(sb.toString());

                          );


                          The idea is to create binary string starting from 0000000 to 1111111 if the input is 7 where 0,1 represents -,+ and start looping. Now create another loop and apply the +/- operations for 1/0 to check if the total is 0 while creating a string from the operations performed. If the total is 0 then print the string that we got from performing the operations.






                          share|improve this answer













                          Brute force approach:



                          var input = 7; // change me

                          var s = "1".repeat(input);
                          IntStream.rangeClosed(0, Integer.parseInt(s, 2))
                          .mapToObj(e ->
                          var str = Integer.toBinaryString(e);
                          return "0".repeat(input - str.length()) + str; // padding zeros
                          )
                          .forEach(binStr ->
                          var total = 0;
                          var plusMinus = binStr.split(""); // splitting binary string to String[]
                          var sb = new StringBuilder();
                          for(int i = 0; i < plusMinus.length; i++)
                          var pm = plusMinus[i].equals("1") ? "+": "-";
                          var j = i + 1;
                          total = pm.equals("+") ? (total + j): (total - j);
                          sb.append(pm).append(j);

                          sb.append(" = ").append(total);
                          if(total == 0)
                          System.out.println(sb.toString());

                          );


                          The idea is to create binary string starting from 0000000 to 1111111 if the input is 7 where 0,1 represents -,+ and start looping. Now create another loop and apply the +/- operations for 1/0 to check if the total is 0 while creating a string from the operations performed. If the total is 0 then print the string that we got from performing the operations.







                          share|improve this answer












                          share|improve this answer



                          share|improve this answer










                          answered yesterday









                          Aniket SahrawatAniket Sahrawat

                          6,15521339




                          6,15521339












                          • This approach takes same amount of time as a recursive method in java. STRANGE.

                            – roundAbout
                            yesterday






                          • 1





                            @roundAbout But recursion is a cleaner approach.

                            – Aniket Sahrawat
                            yesterday











                          • @roundAbout it does the same amount of work, it's just an iterative implementation of the same algorithm.

                            – Baldrickk
                            yesterday

















                          • This approach takes same amount of time as a recursive method in java. STRANGE.

                            – roundAbout
                            yesterday






                          • 1





                            @roundAbout But recursion is a cleaner approach.

                            – Aniket Sahrawat
                            yesterday











                          • @roundAbout it does the same amount of work, it's just an iterative implementation of the same algorithm.

                            – Baldrickk
                            yesterday
















                          This approach takes same amount of time as a recursive method in java. STRANGE.

                          – roundAbout
                          yesterday





                          This approach takes same amount of time as a recursive method in java. STRANGE.

                          – roundAbout
                          yesterday




                          1




                          1





                          @roundAbout But recursion is a cleaner approach.

                          – Aniket Sahrawat
                          yesterday





                          @roundAbout But recursion is a cleaner approach.

                          – Aniket Sahrawat
                          yesterday













                          @roundAbout it does the same amount of work, it's just an iterative implementation of the same algorithm.

                          – Baldrickk
                          yesterday





                          @roundAbout it does the same amount of work, it's just an iterative implementation of the same algorithm.

                          – Baldrickk
                          yesterday











                          1














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



                          Lets look at your example before we impliment 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.






                          share|improve this answer



























                            1














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



                            Lets look at your example before we impliment 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.






                            share|improve this answer

























                              1












                              1








                              1







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



                              Lets look at your example before we impliment 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.






                              share|improve this answer













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



                              Lets look at your example before we impliment 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.







                              share|improve this answer












                              share|improve this answer



                              share|improve this answer










                              answered yesterday









                              EritreanEritrean

                              3,83711015




                              3,83711015





















                                  0














                                  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();







                                  share|improve this answer





























                                    0














                                    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();







                                    share|improve this answer



























                                      0












                                      0








                                      0







                                      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();







                                      share|improve this answer















                                      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();








                                      share|improve this answer














                                      share|improve this answer



                                      share|improve this answer








                                      edited yesterday

























                                      answered yesterday









                                      Ebraheem Alrabee'Ebraheem Alrabee'

                                      627924




                                      627924



























                                          draft saved

                                          draft discarded
















































                                          Thanks for contributing an answer to Stack Overflow!


                                          • Please be sure to answer the question. Provide details and share your research!

                                          But avoid


                                          • Asking for help, clarification, or responding to other answers.

                                          • Making statements based on opinion; back them up with references or personal experience.

                                          To learn more, see our tips on writing great answers.




                                          draft saved


                                          draft discarded














                                          StackExchange.ready(
                                          function ()
                                          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55354283%2ftotal-of-all-numbers-from-1-to-n-will-always-be-zero%23new-answer', 'question_page');

                                          );

                                          Post as a guest















                                          Required, but never shown





















































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown

































                                          Required, but never shown














                                          Required, but never shown












                                          Required, but never shown







                                          Required, but never shown







                                          -java

                                          Popular posts from this blog

                                          Frič See also Navigation menuinternal link

                                          Identify plant with long narrow paired leaves and reddish stems Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) Announcing the arrival of Valued Associate #679: Cesar Manara Unicorn Meta Zoo #1: Why another podcast?What is this plant with long sharp leaves? Is it a weed?What is this 3ft high, stalky plant, with mid sized narrow leaves?What is this young shrub with opposite ovate, crenate leaves and reddish stems?What is this plant with large broad serrated leaves?Identify this upright branching weed with long leaves and reddish stemsPlease help me identify this bulbous plant with long, broad leaves and white flowersWhat is this small annual with narrow gray/green leaves and rust colored daisy-type flowers?What is this chilli plant?Does anyone know what type of chilli plant this is?Help identify this plant

                                          fontconfig warning: “/etc/fonts/fonts.conf”, line 100: unknown “element blank” The 2019 Stack Overflow Developer Survey Results Are In“tar: unrecognized option --warning” during 'apt-get install'How to fix Fontconfig errorHow do I figure out which font file is chosen for a system generic font alias?Why are some apt-get-installed fonts being ignored by fc-list, xfontsel, etc?Reload settings in /etc/fonts/conf.dTaking 30 seconds longer to boot after upgrade from jessie to stretchHow to match multiple font names with a single <match> element?Adding a custom font to fontconfigRemoving fonts from fontconfig <match> resultsBroken fonts after upgrading Firefox ESR to latest Firefox