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} } 

하지만 다른 langage 수 있습니다.

내 코드는 현재 내가 알고있는 것처럼

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

, 당신은 정확히 k 숫자 n을 분할 할 각 적어도 하나 (1).

먼저 n >= k과 k >= 1을 확인합니다. 그렇지 않으면 가능하지 않기 때문에 (구석의 경우 n = k = 0으로 두십시오).

prefix에 정확히 하나의 숫자를 추가하기 때문에 재귀 호출에서 정확하게 k 개의 파티션으로 끝나는 지 확인하려면 두 번째 인수로 max - 1을 전달해야한다고 생각합니다.

다른 문제가있을 수 있습니다. 현재 출력을 알려 주시면보기가 더 쉬울 수 있습니다.