如何修改此java方法中的第一個循環爲遞歸調用？

Question

這是我正在採取的算法課程的一個問題，我無法弄清楚。

// modify the array x to generate the next k-combination from x. 
// In general, the first k-combination of n elements is { 1, 2, ..., k } 
// and the last k-combination is { n-k+1, n-k+2, ..., n }. 
public static boolean nextCombination (int x[], int k, int n) { 
    for (int j = k-1; j >= 0; j--) 
     if (x[j] <= (n - k + j)) { 
      x[j]++; 
      for (int i = 1; i < k - j; i++) 
        x[i+j] = x[j]+i; 
      return true; 
     } 
    return false; 
} 

它被調用通過這種方法：

// print all k-combinations of n elements. 
public static void enumerateCombinations (int k, int n) { 
    int x[] = new int[100]; // k <= 100 
    System.out.println("All " + k + "-combinations of " + n + " numbers:"); 
    for (int j = 0; j < k; j++) 
     x[j] = j+1; 
    while (true) { 
     printArray(x, k); 
     if (nextCombination(x, k, n) == false) 
      break; 
    } 
} 

任何幫助，將不勝感激。

Answer 1

通過此代碼，您可以將nextCombination方法轉換爲遞歸方法。

public static boolean nextCombinationRecursive (int j, int x[], int k, int n) { 
    if (j < 0 || j > k) return false; 

    if (x[j] <= (n - k + j)) { 
     x[j]++; 
     for (int i = 1; i < k - j; i++) 
      x[i+j] = x[j]+i; 
     return true; 
    } 

    return nextCombinationRecursive(j - 1, x, k, n); 
} 

你從enumerateCombinations這樣稱呼它：

if (nextCombinationRecursive(k - 1, x, k, n) == false)