求数组元素和等于目标值的组合：伪代码及C#实现咨询

Hey Joe, 你碰到的是经典的子集和问题，不过你需要的是找出所有能相加等于目标值的元素组合，而不只是判断有没有这样的组合。下面我给你梳理伪代码思路和对应的C#实现，刚好适配你说的1到65的数组场景~

伪代码思路（回溯法） #

回溯法是解决这类“找所有组合”问题的常用方式，核心是枚举所有可能的选择（选当前元素/不选当前元素），并通过剪枝减少不必要的计算：

// 输入：待处理数组arr，目标和target
// 输出：所有和为target的元素组合列表

function findSubsetSums(arr, target):
    将arr按升序排序（方便后续剪枝，遇到大于剩余目标值的元素直接停止）
    初始化结果集合result = []
    
    // 递归回溯函数：参数为当前处理索引、当前组合、剩余需要凑的数值
    function backtrack(currentIndex, currentCombination, remainingTarget):
        // 终止条件1：剩余目标值为0，找到有效组合
        if remainingTarget == 0:
            将currentCombination的副本加入result
            return
        // 终止条件2：剩余目标值为负，或者索引越界，直接返回
        if remainingTarget < 0 or currentIndex >= arr.length:
            return
        
        // 选择1：将当前元素加入组合，继续处理下一个元素
        把arr[currentIndex]加入currentCombination
        backtrack(currentIndex + 1, currentCombination, remainingTarget - arr[currentIndex])
        
        // 回溯：移除刚加入的元素，尝试另一种选择
        从currentCombination中移除arr[currentIndex]
        
        // 选择2：不选当前元素，直接处理下一个元素
        backtrack(currentIndex + 1, currentCombination, remainingTarget)
    
    // 启动回溯
    backtrack(0, [], target)
    返回result

C# 完整实现代码 #

下面是针对你的场景的可运行C#代码，包含生成1-65数组、计算目标值10的所有组合的逻辑：

using System;
using System.Collections.Generic;
using System.Linq;

class SubsetSumFinder
{
    static void Main(string[] args)
    {
        // 生成1到65的数组
        int[] numberArray = Enumerable.Range(1, 65).ToArray();
        int targetSum = 10;
        
        // 获取所有符合条件的组合
        List<List<int>> validCombinations = FindAllSubsetSums(numberArray, targetSum);
        
        // 打印结果
        Console.WriteLine($"所有和为{targetSum}的元素组合：");
        foreach (var combo in validCombinations)
        {
            Console.WriteLine($"{string.Join(" + ", combo)} = {targetSum}");
        }
    }
    
    static List<List<int>> FindAllSubsetSums(int[] arr, int target)
    {
        // 排序数组，优化剪枝效率
        Array.Sort(arr);
        List<List<int>> result = new List<List<int>>();
        
        // 调用回溯函数
        Backtrack(arr, target, 0, new List<int>(), result);
        
        return result;
    }
    
    static void Backtrack(int[] arr, int remainingTarget, int currentIndex, List<int> currentCombo, List<List<int>> result)
    {
        // 找到有效组合，加入结果集
        if (remainingTarget == 0)
        {
            result.Add(new List<int>(currentCombo));
            return;
        }
        
        // 剪枝：剩余目标值为负或索引越界，直接终止
        if (remainingTarget < 0 || currentIndex >= arr.Length)
        {
            return;
        }
        
        // 选择当前元素，递归处理下一个索引
        currentCombo.Add(arr[currentIndex]);
        Backtrack(arr, remainingTarget - arr[currentIndex], currentIndex + 1, currentCombo, result);
        
        // 回溯：移除当前元素，尝试不选它的分支
        currentCombo.RemoveAt(currentCombo.Count - 1);
        
        // （可选）如果数组有重复元素，这里可以跳过重复值避免重复组合
        // while (currentIndex + 1 < arr.Length && arr[currentIndex] == arr[currentIndex + 1])
        // {
        //     currentIndex++;
        // }
        
        // 不选择当前元素，递归处理下一个索引
        Backtrack(arr, remainingTarget, currentIndex + 1, currentCombo, result);
    }
}

额外说明 #

• 剪枝优化：因为数组已经排序，当处理到某个元素大于剩余目标值时，后续所有元素都会更大，完全可以提前终止该分支的递归，这会大幅提升效率（比如目标值是10时，处理到11就直接停止，不用再遍历后面的元素）。
• 时间复杂度：理论上是O(2^n)，但实际因剪枝优化会远低于这个数值，尤其是目标值较小时，像你例子中的目标值10，运行速度会非常快。
• 重复元素处理：如果你的数组存在重复元素，只需解开代码中注释的去重逻辑，就能避免生成重复的组合。

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