1

Требуется с помощью рекурсии определить можно ли из массива 1..N, в котором лежать целые неотрицательные числа, получить сумму K. Никак не могу найти алгоритм для определения возможности получить число из суммы других чисел.

1 ответ 1

2

Не надо суммировать, вычитайте

public bool CangetSumOfK(int[] data, int k, int index = 0)
{
    if (k == 0) return true;
    if (k < 0) return false;
    if (index >= data.Length) return false;

    return CangetSumOfK(data, k, index+1) 
    || CangetSumOfK(data, k - data[index], index+1); 
}

Как использовать

var data = new int[] {1, 2, 3, 4, 5, 6};    
Console.WriteLine(CangetSumOfK(data, 11));
Console.WriteLine(CangetSumOfK(data, 110));

Вывод

True
False

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.