How to find the exact number of numbers that satisfy the condition?

Question

I have a given number of integers in an array. Let's say: {1, 2, 3, 4, 5, 6, 7 }. Note this is just an example they might not be consecutive numbers.

I need to find the numbers that are satisfying the following conditions:

1. The numbers have a set sum.
2. The count of the numbers should be specified.

So with the given numbers above:

1. If the sum is 7 and the number count is 2 it should output {1, 6}.
2. If the sum is 7 and the number count is 3 it should output {1, 2, 4}.
3. If the sum is 7 and the number count is 1 it should output {7}.

I found out similar thread: algorithm to find the correct set of numbers. However the algorithms there doesn't have the requirement for specifying the number count. Here is the algorithm thanks to Lajos Arpad:

public static List<int> backtrack(List<int> currentNumbers, int[] numbers, int depth, int targetValue, int j)
    {
        for (int i = j; i < numbers.Length; i++)
        {
            int potentialSolution = numbers[i];
            if (currentNumbers.Sum() + potentialSolution > targetValue)
            {
                continue;
            }
            else if (currentNumbers.Sum() + potentialSolution == targetValue)
            {
                /*Store solution*/
                currentNumbers.Add(potentialSolution);

                return currentNumbers;
            }
            else
            {
                currentNumbers.Add(potentialSolution);

                return backtrack(currentNumbers, numbers, depth + 1, targetValue, i + 1);
            }
        }

        return null;
    }

Can someone please help me to modify it to add the extra numbers count condition?

Answer 1

Thanks to Rufus L and his post here. It was a simple modification to his code.

    private static void GetSumsRecursively(
        List<int> numbers,
        int sum, 
        List<int> candidates, 
        int numbersCount,
        List<List<int>> results)
    {
        int candidateSum = candidates.Sum(x => x);

        if (candidateSum == sum && candidates.Count == numbersCount)
        {
            results.Add(candidates);
        }

        if (candidateSum >= sum)
            return;

        for (int i = 0; i < numbers.Count; i++)
        {
            var remaining = new List<int>();

            for (int j = i + 1; j < numbers.Count; j++)
            {
                remaining.Add(numbers[j]);
            }

            var filteredCandidates = new List<int>(candidates) { numbers[i] };

            GetSumsRecursively(remaining, sum, filteredCandidates,
                numbersCount, results);
        }
    }

    public static List<List<int>> GetNumbers(
        List<int> numbers,
        int numbersCount, 
        int sum)
    {
        if (numbers == null) throw new ArgumentNullException("numbers");

        var results = new List<List<int>>();

        // Fail fast argument validation
        if (numbersCount < 1 ||
            numbersCount > numbers.Count /*||
            sumDifficulty < numQuestions * Question.MinDifficulty ||
            sumDifficulty > numQuestions * Question.MaxDifficulty*/)
        {
            return results;
        }

        // If we only need single questions, no need to do any recursion
        if (numbersCount == 1)
        {
            results.AddRange(numbers.Where(q => q == sum)
                .Select(q => new List<int> { q }));

            return results;
        }

        // We can remove any questions who have a difficulty that's higher
        // than the sumDifficulty minus the number of questions plus one
        var candidateQuestions =
            numbers.Where(q => q <= sum - numbersCount + 1)
                .ToList();

        if (!candidateQuestions.Any())
        {
            return results;
        }

        GetSumsRecursively(candidateQuestions, sum, new List<int>(),
            numbersCount, results);

        return results;
    }