如何在Kotlin中高效生成和为12的1、2、3所有组合列表

核心思路：回溯剪枝+列表复用 #

要生成所有由1、2、3组成且元素和为12的列表，最高效的方式是用回溯法配合剪枝优化，同时复用同一个列表对象减少内存开销，避免频繁创建新列表。

具体逻辑：

• 维护当前正在构建的列表和当前元素的总和
• 依次尝试添加1、2、3中的一个数，若添加后总和不超过12则继续递归
• 当总和等于12时，将当前列表的副本存入结果集（后续还要修改原列表，必须存副本）
• 递归返回后，移除刚添加的数，继续尝试下一个可能的数

Kotlin 实现代码 #

fun generateCombinations(targetSum: Int): List<List<Int>> {
    val result = mutableListOf<List<Int>>()
    val current = mutableListOf<Int>()

    fun backtrack(currentSum: Int) {
        when {
            currentSum == targetSum -> {
                result.add(current.toList())
                return
            }
            currentSum > targetSum -> {
                return
            }
            else -> {
                listOf(1, 2, 3).forEach { num ->
                    current.add(num)
                    backtrack(currentSum + num)
                    current.removeLast()
                }
            }
        }
    }

    backtrack(0)
    return result
}

// 测试调用
fun main() {
    val combinations = generateCombinations(12)
    combinations.forEach { println(it) }
}

实现优势说明 #

1. 剪枝优化：当当前总和超过12时直接终止分支递归，避免无效计算
2. 内存高效：复用同一个current列表构建所有组合，仅在找到有效组合时创建副本，大幅减少对象创建开销
3. 递归深度可控：最大递归深度为12（全选1的情况），不会出现栈溢出问题

可选：动态规划实现（逻辑直观但内存开销稍大） #

如果更倾向于迭代方式，可使用动态规划，但会生成较多中间列表：

fun generateCombinationsDP(targetSum: Int): List<List<Int>> {
    val dp = Array(targetSum + 1) { mutableListOf<List<Int>>() }
    dp[0].add(emptyList())

    for (n in 1..targetSum) {
        if (n >= 1) dp[n].addAll(dp[n-1].map { it + 1 })
        if (n >= 2) dp[n].addAll(dp[n-2].map { it + 2 })
        if (n >= 3) dp[n].addAll(dp[n-3].map { it + 3 })
    }

    return dp[targetSum]
}

该方法逻辑清晰，但每个步骤都会创建新列表，内存开销比回溯法高，当目标值较大时差异更明显。

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