如何将静态硬编码函数改写为递归函数，生成n个单词分任意行的有序组合

我需要基于Knuth（Tex）最小粗糙度换行算法实现不同长度文本适配不同尺寸圆形的自动换行，目前卡在将硬编码的嵌套循环函数改造为动态递归版本的环节。
需求是列出n个单词拆分到k行的所有合法组合，组合用每行起始单词下标构成的数组L[]存储，需满足以下约束：

• 每行必须至少包含1个单词
• 单词顺序不可调换（保证L.length <= n即可）

示例参考 #

以5个单词（下标0-4）拆分到3行（下标0-2）为例，共有6种合法组合：

Line0  Line1  Line2 
   0      1    2+3+4 
   0     1+2    3+4  
   0    1+2+3    4   
  0+1     2     3+4  
  0+1    2+3     4   
 0+1+2    3      4   

对应的输出的L数组集合应为[[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4]]

现有硬编码实现（仅支持3行场景） #

// 仅支持固定3行拆分（L[0]到L[2]）
const n = 5; // 单词总数
var L = [0], ret = []; // 第0行固定从单词下标0开始
for(L[1] = L[0]+1; L[1] < n; L[1]++){            // 遍历第1行的所有合法起始下标
  for(L[2] = L[1]+1; L[2] < n; L[2]++){          // 遍历第2行的所有合法起始下标
    ret.push([...L]); // 注意需拷贝数组，避免引用类型导致所有元素指向同一个数组
  }
}                    
console.log(ret);

核心思路是逐层确定每一行的起始下标，每确定一行就递归到下一层，直到凑齐k行的起始下标就存入结果集，逻辑如下：

/**
 * 生成n个单词拆分为k行的所有合法起始下标组合
 * @param {number} n 单词总数
 * @param {number} k 拆分的总行数
 * @returns {Array<Array<number>>} 所有合法的L数组组合
 */
function generateLineStarts(n, k) {
  const result = [];
  /**
   * 递归回溯函数
   * @param {number} currentLine 当前处理到第几行（从1开始，第0行已固定为0）
   * @param {Array<number>} currentStarts 已确定的行起始下标数组
   */
  function dfs(currentLine, currentStarts) {
    // 终止条件：已经凑齐k行的起始下标，存入结果集
    if (currentLine === k) {
      result.push([...currentStarts]);
      return;
    }
    const prevLineStart = currentStarts[currentLine - 1];
    // 本行起始下标的最大值：需要预留足够单词给剩余的行，每行至少1个
    const maxValidStart = n - (k - currentLine);
    for (let currentStart = prevLineStart + 1; currentStart <= maxValidStart; currentStart++) {
      currentStarts.push(currentStart);
      dfs(currentLine + 1, currentStarts);
      currentStarts.pop(); // 回溯，清除当前选择尝试下一个可能
    }
  }
  // 边界校验：行数不能小于1，也不能大于单词总数（每行至少1个单词）
  if (k < 1 || k > n) return result;
  // 第0行固定从下标0开始，从第1行开始递归处理
  dfs(1, [0]);
  return result;
}

测试验证 #

调用generateLineStarts(5, 3)，输出结果和预期完全一致：

[[0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4]]

扩展场景测试：n=4、k=2时，输出为[[0,1],[0,2],[0,3]]，符合业务要求。

内容的提问来源于stack exchange，提问作者ashleedawg