Найти все возможные пути Алгоритм

Question

Здравствуйте, StackOverFlow! Я размещаю здесь сегодня, потому что у меня проблема здесь, на Java, где я пытаюсь вычислить все возможные комбинации палочек pogo, которые мой персонаж может использовать для перемещения. Символ использует pogo sticks, все из которых имеют дистанцию, заданную пользователем.

Аналогичным образом, общее расстояние также предоставляется через пользовательский ввод, и все возможные пути должны быть найдены. Я показал свою функцию ниже с выходом и желаемым результатом, который, похоже, не совсем прав.

Я застрял на этой проблеме некоторое время, и я действительно надеюсь, что кто-то может помочь мне здесь!

/* 
* First integer in input 
*/ 
int totalDistance; 

/* 
* The remaining integers in the input 
*/ 
ArrayList<Integer> pogoSticks = new ArrayList<Integer>(); 

private void findPaths() { 
     ArrayList<ArrayList<Integer>> possibleSticks = new ArrayList<ArrayList<Integer>>(); 

     for (int i = 0; i < pogoSticks.size(); i++) { 

      int pogoStickDistance = pogoSticks.get(i); 

      if (pogoStickDistance == totalDistance) { 
       if (!possibleSticks.contains(new ArrayList<Integer>(pogoStickDistance))) { 
        ArrayList<Integer> list = new ArrayList<Integer>(); 
        list.add(pogoStickDistance); 
        possibleSticks.add(list); 
       } 
      } else if (pogoStickDistance < totalDistance) { 
       int remainingDistance = totalDistance; 
       ArrayList<Integer> possibleSubSticks = new ArrayList<Integer>(); 

       possibleSubSticks.add(pogoStickDistance); 
       remainingDistance -= pogoStickDistance; 

       for (int j = 0; j < pogoSticks.size(); j++) { 

        int pogoStickDistance1 = pogoSticks.get(j); 
        if (pogoStickDistance1 == remainingDistance) { 
         possibleSubSticks.add(pogoStickDistance1); 

         possibleSticks.add(possibleSubSticks); 
         break; 
        } else if (pogoStickDistance1 < remainingDistance) { 
         possibleSubSticks.add(pogoStickDistance1); 
         remainingDistance -= pogoStickDistance1; 
        } 

        if (j == (pogoSticks.size() - 1) && pogoStickDistance1 != remainingDistance) { 
         j = 0; 
        } 
       } 
      } 

     } 

     System.out.println(possibleSticks); 
    } 

Вот вывод, что я получаю от работы функции выше:

Enter input: 5 10 4 1 2 
[[4,1], [1,4], [2,1,2]] 

Обратите внимание, что 5 расстояние, и 10, 4, 1 и 2 являются расстояниями, что пого палка может путешествовать.

Проблема в том, что это не все возможные пути! Например, отсутствуют такие пути, как [1, 1, 1, 1, 1] или [2, 2, 1].

Может ли кто-нибудь помочь мне изменить мою функцию, чтобы включить их? Я считаю, что это происходит потому, что, как только моя петля обнаруживает, что первое появление расстояния полого-палочки меньше, чем оставшееся расстояние, оно немедленно использует этот путь и игнорирует другие возможности.

Answer 1

   for(int i = 0;i < pogoSticks.size();i++){ 
        //part to calculate small enough 
     int[] temps = new int[pogoSticks.size]; 
     int temp1 = 0; 
        for(int j; j< pogoStricks.size();i++){ 
        if(pogoSticks.getIndex(j) + k <= totalDisatnce){ 
     temps[temp1] = pogoSticks.getIndex(j); 
     } 
    //code to calculate number of paths to get to TotalDistance 

Это должно выполнить половину работы, теперь вам просто нужен способ вычисления расстояния от всех переменных temps. Я предлагаю вам вычесть каждое значение из TotalDistance и посмотреть, какие числа добавили бы это.