C#查找数字列表中和为目标值的组合算法优化问询

原实现存在的核心问题 #

• 未对输入数组排序，优先遍历小数会拉长搜索路径，你举的例子中就因为先遍历0.56，错过了90+10的短路径匹配
• 递归过程中频繁创建新列表、执行Remove操作，内存和时间开销极高
• 下标传递逻辑错误，递归时传入startIndex++会导致重复遍历相同元素，产生大量冗余计算

优化后实现 #

public class Solver {
    private List<List<decimal>> mResults;
    private decimal[] _sortedElements;

    public List<List<decimal>> Solve(decimal goal, decimal[] elements) {
        mResults = new List<List<decimal>>();
        // 预处理：过滤大于目标值的无效元素，再降序排序，优先尝试大数组合
        _sortedElements = elements.Where(x => x <= goal).OrderByDescending(x => x).ToArray();
        // 用下标控制可选范围，不需要额外维护notIncluded列表
        RecursiveSolve(goal, 0.0m, new List<decimal>(), 0);
        return mResults; 
    }

    private void RecursiveSolve(decimal goal, decimal currentSum, List<decimal> included, int startIndex) {
        // 已找到结果，直接终止所有递归
        if (mResults.Count > 0) return;

        for (int index = startIndex; index < _sortedElements.Length; index++) {
            decimal nextValue = _sortedElements[index];
            decimal newSum = currentSum + nextValue;

            if (newSum == goal) {
                // 命中匹配，存入结果
                List<decimal> newResult = new List<decimal>(included);
                newResult.Add(nextValue);
                mResults.Add(newResult);
                return;
            }
            else if (newSum < goal) {
                // 回溯递归：先加入当前元素，从下一个下标开始遍历避免重复选
                included.Add(nextValue);
                RecursiveSolve(goal, newSum, included, index + 1);
                // 递归返回后移除当前元素，尝试下一个选项
                included.RemoveAt(included.Count - 1);
            }
        }
    }
}

优化点说明 #

• 降序排序后优先尝试大数组合，你举的测试场景排序后数组顺序为[90,10,0.56]，遍历到第二个元素即可直接命中结果，完全不需要遍历后续元素
• 改用回溯+下标控制的方式替代原有的列表复制、删除操作，内存开销从O(n²)降至O(n)，遍历效率提升数倍
• 修复了下标传递错误，严格控制每次递归从当前元素的下一个位置开始遍历，既不会重复选元素也不会产生无效遍历

如果需要进一步提升性能，可以额外增加前缀和剪枝逻辑：提前计算每个下标到数组末尾的元素总和，如果当前累加值加上剩余所有元素的总和仍小于目标值，直接终止当前分支的遍历即可。

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