Sum of K elements in array that equates to N

algorithm, c#, data-structures, recursion

Solution

You function looks fine but possible a bit optimize:

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

Also I fixed a bug in your function. It fails on following testcase:

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

Your functions returns only `{10}` instead of `{10} and {10, 2, -2}`

Problem

Given an array say nums = { 1,2,5,3,6,-1,-2,10,11,12}, using max no of elements (say maxNums=3) find the elements whose sum (say sum =10) = K so if maxNums to be used = 3 sum to find = 10 the the answer is ``` {1 3 6} {1 -1 10} {1 -2 11} {2 5 3} {2 -2 10} {5 6 -1} {-1 11} {-2 12} {10} ``` I wrote a recursive function which does the job. How do I do it without recursion? and/or with less memory ? ``` 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); } } ```

Original source