title: Why doesn't my search algorithm work for Project Euler 31?
body: <p>Problem 31</p>
  
  <blockquote>
    <p>In England the currency is made up of pound, £, and pence, p, and
    there are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p,
    50p, £1 (100p) and £2 (200p). It is possible to make £2 in the
    following way: 1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p How many
    different ways can £2 be made using any number of coins?</p>
  </blockquote>
  
  <pre><code>static int[] nums = {200,100,50,20,10,5,2,1};
  static int size = nums.length;
  static HashMap&lt;Integer,Integer&gt; pivots = new HashMap&lt;&gt;();
  
  public static int checkSum(HashMap&lt;Integer,Integer&gt; pivots){
  
      int target = 200;
      int sum = 0;
  
      for(Integer key: pivots.keySet()){
          int pivot = pivots.get(key);
          sum +=  nums[pivot];
          if(sum &gt; target) return 1;
      }
  
      if(sum &lt; target) return -1;
  
      return 0;
  }
  
  public static void shift(HashMap&lt;Integer,Integer&gt; pivots, int pivot_node){
  
      if(pivots.size() + nums[pivots.get(1)] == 201 &amp;&amp; pivots.get(1) != 0){
  
          int p_1_value = pivots.get(1);   //this part checks whether the  current node(which is the first node)                                                                  
                                    //has reached children of all 1. 
                               //Which means it's time to shift the root node.
          pivots.clear();
          pivots.put(1 , p_1_value);
          shift(pivots, 1);
          return;
      }
  
      if(pivots.get(pivot_node) != size - 1) {
          pivots.put(pivot_node, pivots.get(pivot_node) + 1);
      }
      else{
          shift(pivots , pivot_node - 1);
      }
  
  }
  
  
  
  public static void branch(HashMap&lt;Integer,Integer&gt; pivots){
      pivots.put(pivots.size() + 1, pivots.get(pivots.size()));
  }
  
  public static int search(){
      int bool = checkSum(pivots);
  
      int n = 0;
      int count = 0;
  
      while(n &lt; 25) {
          count++;
          if (bool == 0) {
              n++;     // if the sum is equal to 200, we shift the last 
                       //pivot to the next lower number.               
              shift(pivots, pivots.size());
  
          }else if (bool == -1) {   
              branch(pivots); //if the sum is less than 200, we make a new pivot with value of the last pivot.
          }else if (bool == 1) {    
              shift(pivots, pivots.size());  //if the sum is greater than 200,
                                            //we shift to the last pivot to the next lower number. 
          }
          bool = checkSum(pivots);
      }
      return n;
  }
  
  public static void main(String[] args){
  
      pivots.put(1,0);
  
      int n = search();
  
      System.out.print("\n\n------------\n\n"+ "n: " + n);
  
  }
  </code></pre>
  
  <p>This is an algorithm that searches for combinations of a set that add up to a target. It's kind of like a depth first tree search without using a tree. Each pivot represents node on the "tree". The shift() method changes the value of the node to the next lower value. The branch() method creates a new node with the same value of the last node. The checkSum() method checks whether the sum of the pivots are &lt;,= or > the target, 200. </p>
  
  <p>The correct answer for the number of ways is supposed to be around 73000. But my algorithm only returns about 300 ways.
  I have no idea why this happens because my algorithm should reach every single possible combination that equals 200.</p>
  
  <p>This is a visualization of how my algorithm works:</p>
  
  <p><img src="https://i.stack.imgur.com/iqtVn.jpg" alt="img"></p>