Проверить может ли число быть представлено как сумма некоторых из чисел массива

@RedBaron · Регистрация: 25.04.2020

Author24 — интернет-сервис помощи студентам

Необходимо решить задачу, используя рекурсию.

Дан массив из n целых положительных чисел a[1]…a[n] и число s. Требуется узнать, может ли число s быть представлено как сумма некоторых из чисел массива a. (Каждое число можно использовать не более чем по одному разу.)

В интернете предлагается вот такой способ решения, но не могу понять, как его применить.

Кликните здесь для просмотра всего текста

Будем задавать k-позицию последовательностью из k
булевских значений, определяющих, входят ли в сумму числа
a[1]..a[k] или не входят. Позиция допустима, если ее сумма не
превосходит s.

@Bleach163 · 25.05.2021, 09:02

Сообщение от RedBaron

В интернете предлагается вот такой способ решения

Мне кажется, подразумевалось решение через динамическое программирование, которое, как бы, не использует рекурсию.
Через рекурсию будет что-то вроде...

C++

bool rec(int arr[], int n, int s, int i = 0)
{
    if (s <= 0 || i >= n)
        return s == 0;
    return rec(arr, n, s - arr[i], i + 1) || rec(arr, n, s, i + 1);
}

@RedBaron 0 / 0 / 0 Регистрация: 25.04.2020 Сообщений: 6
		1
	Проверить может ли число быть представлено как сумма некоторых из чисел массива 24.05.2021, 23:00. Показов 1457. Ответов 1 Метки нет (Все метки) Необходимо решить задачу, используя рекурсию. Дан массив из n целых положительных чисел a[1]…a[n] и число s. Требуется узнать, может ли число s быть представлено как сумма некоторых из чисел массива a. (Каждое число можно использовать не более чем по одному разу.) В интернете предлагается вот такой способ решения, но не могу понять, как его применить. Кликните здесь для просмотра всего текста Будем задавать k-позицию последовательностью из k булевских значений, определяющих, входят ли в сумму числа a[1]..a[k] или не входят. Позиция допустима, если ее сумма не превосходит s. 0

	25.05.2021, 09:02