如何系统找出和为指定值的数集的所有组合？

你问的这个问题其实是经典的子集和问题（Subset Sum Problem），属于组合优化领域的常客，确实有成熟的系统方法能搞定——不管是你这种小规模的数字集合，还是大规模的海量数据，都有对应的思路。

一、回溯法：适合小规模数据，精准找出所有组合 #

回溯法可以理解为“聪明的暴力枚举”，通过递归尝试每个数字“选”或“不选”，同时通过剪枝跳过不必要的计算，效率比纯暴力高不少。

拿你的例子来说：

• 先把数字按从大到小排序：36,27,12,6,4,2，目标和是39
• 第一个数字36，选的话36>39，直接跳过（剪枝）；
• 选27之后，目标和剩下12，接下来看后面的数字：选12刚好凑够39，得到集合{27,12}；如果不选12，选6之后目标剩6，再选4剩2，选2刚好凑齐，得到{27,6,4,2}；
• 再往后的数字（比如12单独是12<39，12+6+4+2=24<39），组合起来都达不到目标，直接排除。

用伪代码大概是这样的（方便你理解逻辑）：

function backtrack(nums, start_idx, remaining_target, current_path, result_list):
    if remaining_target == 0:
        result_list.append(current_path.copy())
        return
    if remaining_target < 0:
        return
    # 从start_idx开始，避免重复组合（比如{27,12}和{12,27}算同一个）
    for i in range(start_idx, len(nums)):
        # 如果有重复数字，跳过避免生成重复子集
        if i > start_idx and nums[i] == nums[i-1]:
            continue
        current_path.append(nums[i])
        # 递归处理下一个数字，目标和减去当前选中的数字
        backtrack(nums, i+1, remaining_target - nums[i], current_path, result_list)
        # 回溯，把当前数字从路径中移除，尝试不选它的情况
        current_path.pop()

这个方法的优势是能找出所有符合条件的子集，但缺点也很明显：当元素个数超过20左右时，组合数会指数级增长，速度会变慢。

二、动态规划：适合大规模数据，先判断可行性再找组合 #

如果面对的是大规模数据（比如上百个元素），回溯法就不太现实了，这时候可以用动态规划先判断是否存在符合条件的子集，再结合回溯思想找出所有组合。

步骤1：构建DP表判断可行性 #

我们可以创建一个二维数组dp，其中dp[i][j]表示“用前i个数字能不能凑出和为j”。

• 初始化：dp[0][0] = True（0个数字能凑出和为0），其他位置初始为False；
• 状态转移：对每个数字nums[i-1]（因为数组从0开始），dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i-1]]——意思是要么不选当前数字，用前i-1个数字凑j；要么选当前数字，用前i-1个数字凑j - nums[i-1]。

步骤2：回溯DP表找出所有组合 #

当确认存在可行子集后，我们可以从DP表的最后一行（对应所有数字）开始逆向推导：

• 如果dp[n][target]为True，看dp[n-1][target]是否为True：如果是，说明不选第n个数字也能凑出目标和，继续往前推；如果不是，说明必须选第n个数字，然后把它加入结果集合，再去推dp[n-1][target - nums[n-1]]。

这个方法的时间复杂度是O(n*target)，比回溯法高效很多，尤其是当目标和不是特别大的时候。

三、实用小技巧，进一步优化效率 #

不管用哪种方法，这些小技巧都能帮你更快得到结果：

• 先排序：把数字从大到小排序，能快速跳过那些比当前剩余目标和大的数字，减少不必要的计算；
• 去重处理：如果数字集合里有重复元素，先去重，避免生成重复的子集；
• 提前终止：如果当前剩余目标和小于所有未处理数字的最小值，直接终止这条分支。

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