Soma de elementos K na matriz que equivale a N
Dado um array dizer nums = {1,2,5,3,6, -1, -2,10,11,12}, usando no máximo nenhum dos elementos (digamos maxNums = 3) encontre os elementos cuja soma (digamos sum = 10) = K
Então, se maxNums para ser usado = 3 soma para encontrar = 10 a resposta é
{1 3 6}
{1 -1 10}
{1 -2 11}
{2 5 3}
{2 -2 10}
{5 6 -1}
{-1 11}
{-2 12}
{10}
Eu escrevi uma função recursiva que faz o trabalho.Como faço isso sem recursão? e / ou com menos memória?
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);
}
}