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

给定一个数组说nums = {1,2,5,3,6，-1，-2,10,11,12}，使用max no of elements（比如maxNums = 3）找到其总和的元素（比如sum = 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 = 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); } } 

Answer 1

你的function看起来很好但可能有点优化：

 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); } } } 

我还修复了你的function中的一个错误。 它无法使用以下测试用例：

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

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

Answer 2

而Haskell解决方案……

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

* Main> listElements 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]