c# - 数组中等于 N 的 K 个元素之和

标签 c# algorithm data-structures recursion

给定一个数组 nums = { 1,2,5,3,6,-1,-2,10,11,12},使用最大元素数(比如 maxNums=3) 找到总和(比如总和 =10)= K 的元素

所以如果要使用的 maxNums = 3 求和 = 10 答案是

    {1  3  6}    
    {1  -1  10}
    {1  -2  11}
    {2  5  3}
    {2  -2  10}
    {5 6 -1}
    {-1  11}
    {-2  12}
    {10}

我写了一个递归函数来完成这项工作。 不使用递归我该怎么做? 和/或内存更少?

class Program
{
        static Int32[] nums = { 1,2,5,3,6,-1,-2,10,11,12};
        static Int32 sum = 10;
        static Int32 maxNums = 3;


        static void Main(string[] args)
        {

            Int32[] arr = new Int32[nums.Length];
            CurrentSum(0, 0, 0, arr);

            Console.ReadLine();
        }

        public static void Print(Int32[] arr)
        {
            for (Int32 i = 0; i < arr.Length; i++)
            {
                if (arr[i] != 0)
                    Console.Write("  "   +arr[i]);
            }
            Console.WriteLine();
        }


        public static void CurrentSum(Int32 sumSoFar, Int32 numsUsed, Int32 startIndex, Int32[] selectedNums)
        {
            if ( startIndex >= nums.Length  || numsUsed > maxNums)
            {
                if (sumSoFar == sum && numsUsed <= maxNums)
                {
                    Print(selectedNums);
                }                    
                return;
            }

                       **//Include the next number and check the sum**
                    selectedNums[startIndex] = nums[startIndex];
                    CurrentSum(sumSoFar + nums[startIndex], numsUsed+1, startIndex+1, selectedNums);

                    **//Dont include the next number**
                    selectedNums[startIndex] = 0;
                    CurrentSum(sumSoFar , numsUsed , startIndex + 1, selectedNums);
        }
    }

最佳答案

你的功能看起来不错,但可能有点优化:

class Program
{
    static Int32[] nums = { 1, 2, 5, 3, 6, -1, -2, 10, 11, 12 };
    static Int32 sum = 10;
    static Int32 maxNums = 3;
    static Int32[] selectedNums = new Int32[maxNums];

    static void Main(string[] args)
    {
        CurrentSum(0, 0, 0);
        Console.ReadLine();
    }

    public static void Print(int count)
    {
        for (Int32 i = 0; i < count; i++)
        {
            Console.Write(" " + selectedNums[i]);
        }
        Console.WriteLine();
    }

    public static void CurrentSum(Int32 sumSoFar, Int32 numsUsed, Int32 startIndex)
    {
        if (sumSoFar == sum && numsUsed <= maxNums)
        {
            Print(numsUsed);
        }

        if (numsUsed >= maxNums || startIndex >= nums.Length)
            return;

        for (int i = startIndex; i < nums.Length; i++)
        {
            // Include i'th number
            selectedNums[numsUsed] = nums[i];
            CurrentSum(sumSoFar + nums[i], numsUsed + 1, i + 1);
        }
    }
}

我还修复了您函数中的一个错误。 它在以下测试用例上失败:

{10, 2, -2}
Sum = 10
K = 3

您的函数仅返回 {10} 而不是 {10} 和 {10, 2, -2}

关于c# - 数组中等于 N 的 K 个元素之和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14575931/

相关文章:

c - 树结构和线程

c# - 我可以发送图像和 rar 文件,但这些文件已被 asp.net 损坏?

c# - 如何使用自定义委托(delegate)对没有参数的方法进行 stub ?

c# - 如何通过 Pulumi 在 Function App 中创建主机 key

java - 难以理解合并排序算法的合并部分

python-3.x - 置换算法的Big-O分析

android - 试图找到一个android数据结构

c# - 我已经插入了一行,我想获取它的 ID 并加上一个 int 并插入到该行中

algorithm - 领袖选举算法

.net - .NET 中的双向映射