Java Partition Algorithm

Question

Я ищу рекурсивный алгоритм для разбиения числа на k частей.

Для Exemple:

P(5,2) > { {1,4},{2,3} } 
P(7,2) > { {1,6},{2,5},{3,4} } 
P(5,3) > { {1,1,3},{1,2,2} } 

В Java, но это может быть другой языка сайта.

Мой код в настоящее время

public static void partition(int n, int k) { 
     partition(n, k, " "); 
    } 

    public static void partition(int n, int max, String prefix) { 
     if (n == 0) { 
      System.out.println(prefix); 
      return; 
     } 

     for (int i = Math.min(max, n); i >= 1; i--) { 
      partition(n-i, i, prefix + " " + i); 
     } 
    } 

Answer 1

Как я понимаю, вы хотите разделить n ровно в k чисел, каждое по меньшей мере, один (1).

Я бы сначала проверил, что n >= k и k >= 1, потому что в противном случае это невозможно (оставьте поле для угла n = k = 0).

В вашем рекурсивного вызова, так как вы добавление ровно один номер к prefix, я думаю, вы должны пройти max - 1 в качестве второго аргумента, чтобы убедиться, что вы будете в конечном итоге с точно k перегородками.

Возможны другие проблемы. Если вы сообщите нам свой текущий результат, это может быть проще увидеть.