数组中K个元素的和等于N

Question

数组中K个元素的和等于N

5

给定一个数组，例如nums = { 1,2,5,3,6,-1,-2,10,11,12}，使用最大数量的元素（maxNums = 3），找出元素之和等于K（sum = 10）的元素。

因此，如果要使用的maxNums = 3，要查找的sum = 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);
        }
    }

- SheldonCooper

问题不清楚，而且你使用的语言也不明确。 - Nir Alfasi

我正在使用C#作为编程语言。 - SheldonCooper

7

这是子集和问题，是一个非常著名的问题。有大量的文献介绍如何解决它，但需要注意的是，在其最一般的形式中，它无法快速解决。（也就是说，只有当P == NP时才有快速解决方案，而P几乎肯定不等于NP。） - Eric Lippert

数组中元素的最小和最大可能值是多少？ - Толя

你不关心运行时间，只是想摆脱递归？在这种情况下，我会给你一个提示。考虑存储在堆栈上的内容。将其取出并放入数组中。观察到你的递归不会超过maxNums层。 - thang

2个回答

1

而 Haskell 的解决方案是...

import Data.List
listElements max_num k arr = 
  filter (\x -> sum x == k && length x == max_num) $ subsequences arr

*主要> 列出元素 3 10 [1,2,5,3,6,-1,-2,10,11,12]
[[2,5,3],[1,3,6],[5,6,-1],[1,-1,10],[2,-2,10],[1,-2,11]]

- גלעד ברקן

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Толя · Accepted Answer

您的函数看起来不错，但有一些优化的空间：

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}。