如何在递归函数中统计组合数量？现有打印定长字符组合代码需加计数功能

实现思路 #

你之前计数器失效的核心原因是Java基本类型为值传递，递归过程中修改的是变量副本，无法同步计数结果。下面提供两种可直接落地的实现方案： #

方案1：递归函数返回计数（无额外依赖，最简洁）

调整递归方法的返回值为当前分支生成的有效组合数，逐层累加即可得到总数量，完全不影响原有打印逻辑：

static int printAllPossibilities(String charSet, int length) {
  return printAllPossibilities_(charSet, length, "");
}

static int printAllPossibilities_(String charSet, int length, String temp) {
  if (length == 0) {
    System.out.println(temp);
    // 命中1个有效组合，返回计数1
    return 1;
  }
  int total = 0;
  for (int i = 0; i < charSet.length(); i++) {
    // 累加所有子递归分支的计数
    total += printAllPossibilities_(charSet, length - 1, temp + charSet.charAt(i));
  }
  return total;
}

调用示例：

// 打印所有长度为2的组合，total即为总数量
int total = printAllPossibilities("1234", 2);

方案2：共享可变计数器（保留原方法返回值结构）

如果不想改动原有方法的返回值类型，可以用AtomicInteger作为共享计数器，利用引用传递的特性实现跨递归层级的计数同步：

import java.util.concurrent.atomic.AtomicInteger;

static void printAllPossibilities(String charSet, int length) {
  AtomicInteger counter = new AtomicInteger(0);
  printAllPossibilities_(charSet, length, "", counter);
  // 如果需要拿到总数，也可以调整方法返回counter.get()
  System.out.println("总组合数：" + counter.get());
}

static void printAllPossibilities_(String charSet, int length, String temp, AtomicInteger counter) {
  if (length == 0) {
    System.out.println(temp);
    counter.incrementAndGet();
    return;
  }
  for (int i = 0; i < charSet.length(); i++) {
    printAllPossibilities_(charSet, length - 1, temp + charSet.charAt(i), counter);
  }
}

扩展建议

如果后续需要复用生成的组合做功能开发，可以新增一个List<String>参数传入递归方法，在打印的同时把组合存入列表，避免后续重复生成：

static int printAllPossibilities(String charSet, int length, List<String> resultStore) {
  return printAllPossibilities_(charSet, length, "", resultStore);
}

static int printAllPossibilities_(String charSet, int length, String temp, List<String> resultStore) {
  if (length == 0) {
    System.out.println(temp);
    resultStore.add(temp);
    return 1;
  }
  int total = 0;
  for (int i = 0; i < charSet.length(); i++) {
    total += printAllPossibilities_(charSet, length - 1, temp + charSet.charAt(i), resultStore);
  }
  return total;
}

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