如何通过函数递归简化任意盘子数的分饼干问题代码？

我正在完成一项编程挑战：实现一个函数，以饼干数量和盘子数量为参数，计算将所有饼干分配到指定数量盘子的所有可能组合，要求每个盘子不能为空，且不同顺序的相同组合视为一种（例如[1,2,3]与[3,1,2]视为同一组合）。

当前代码存在大量重复逻辑，只能支持固定数量的盘子，想改成递归实现以支持任意数量的盘子，但不知道具体怎么做。

当前代码 #

function areEqual(array1, array2) {
  return array1.every((element, index) => {
    if (element === array2[index]) return true;
    else return false;
  });
}
console.log(areEqual([1, 2, 3], [1, 2, 3]));

function divideCookies(cookies, plates) {
  // You have to implement this method
  // const possibilities = [];
  const plates2 = (cookies) => {
    const possibilities = [];
    for (let i = 1; i < Math.floor(cookies / 2) + 1; i++) {
      possibilities.push([i, cookies - i]);
    }
    return possibilities;
  };

  const plates3 = (cookies) => {
    const possibilities = [];
    for (let i = 1; i < Math.floor(cookies / 3) + 1; i++) {
      const x = plates2(cookies - i);
      console.log(x);
      x.forEach((plate) => {
        possibilities.push([i, ...plate]);
      });
    }
    for (const arr of possibilities) {
      arr.sort((a, b) => a - b);
    }

    possibilities.sort().forEach((el, i, arr) => {
      if (arr[i + 1]) {
        if (areEqual(el, arr[i + 1])) {
          possibilities.splice(possibilities.indexOf(el), 1);
        }
      }
    });
    return possibilities;
  };
  const plates4 = (cookies) => {
    const possibilities = [];
    for (let i = 1; i < Math.floor(cookies / 4) + 1; i++) {
      const x = plates3(cookies - i);

      x.forEach((plate) => {
        possibilities.push([i, ...plate]);
      });
    }
    for (const arr of possibilities) {
      arr.sort((a, b) => a - b);
    }

    possibilities.sort().forEach((el, i, arr) => {
      if (arr[i + 1]) {
        if (areEqual(el, arr[i + 1])) {
          possibilities.splice(possibilities.indexOf(el), 1);
        }
      }
    });
    return possibilities;
  };

  if (plates === 2) {
    const possibilities = plates2(cookies);
    return possibilities;
  } else if (plates === 3) {
    const possibilities = plates3(cookies);
    return possibilities;
  }
  if (plates === 4) {
    const possibilities = plates4(cookies);
    return possibilities;
  }
  if (plates === 5) {
    const possibilities = plates4(cookies);
    return possibilities;
  }
}

递归实现思路 #

你的代码核心问题是为每个盘子数量写了重复的函数，递归的关键是找到终止条件和递归关系，同时从根源避免重复组合：

1. 终止条件 #

当盘子数量为1时，只有一种分配方式：把所有饼干放在这一个盘子里，直接返回[[cookies]]。

2. 递归关系 #

要分配n个盘子的饼干，先给当前盘子分配i个饼干，再递归计算剩下的cookies - i个饼干分配到plates - 1个盘子的组合。

3. 避免重复的关键 #

限制后续分配的饼干数不小于当前盘子的数量，这样生成的组合天然是非递减的（比如[1,2,3]不会生成[2,1,3]），不需要后续排序去重，效率更高。

重构后的代码 #

function divideCookies(cookies, plates) {
  // 边界判断：盘子数不能大于饼干数，否则无法每个盘子非空
  if (plates > cookies) return [];
  
  // 递归辅助函数
  // remainingCookies: 剩余待分配的饼干数
  // remainingPlates: 剩余的盘子数
  // start: 当前盘子最少可分配的饼干数（保证组合非递减）
  function helper(remainingCookies, remainingPlates, start) {
    // 终止条件：只剩一个盘子，分配所有剩余饼干
    if (remainingPlates === 1) {
      return [[remainingCookies]];
    }
    
    const result = [];
    // 当前盘子最多分配的饼干数：保证后续每个盘子至少能分到start个
    const max = Math.floor(remainingCookies / remainingPlates);
    
    for (let i = start; i <= max; i++) {
      // 递归获取子组合
      const subCombinations = helper(remainingCookies - i, remainingPlates - 1, i);
      // 合并当前分配数与子组合
      subCombinations.forEach(comb => result.push([i, ...comb]));
    }
    
    return result;
  }
  
  // 初始调用：第一个盘子最少分配1个饼干
  return helper(cookies, plates, 1);
}

// 测试示例
console.log(divideCookies(6, 3)); // 输出 [[1,1,4], [1,2,3], [2,2,2]]
console.log(divideCookies(5, 2)); // 输出 [[1,4], [2,3]]
console.log(divideCookies(7, 4)); // 输出 [[1,1,1,4], [1,1,2,3]]

代码说明 #

• 边界处理：先判断盘子数是否大于饼干数，直接返回空数组（无法满足每个盘子非空的要求）。
• 辅助函数helper：通过start参数限制后续分配的最小值，确保生成的组合始终是非递减的，从根源避免重复。
• 循环范围控制：i从start到Math.floor(remainingCookies / remainingPlates)，保证后续每个盘子至少能分到和当前盘子相同数量的饼干，不会出现逆序组合。

重构后的代码支持任意数量的盘子，逻辑简洁，效率远高于原代码的排序去重方式。

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