java - 如何将此java方法中的第一个for循环修改为递归调用？

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)