Question

Даны цело численный массив А [1: n] и число М. Найти множество элементов А [i1], А [i2], ..., А [ik] (1< i1 < ... < ik < n), что А [i1] + А [i2] + ... А [ik] = М.

Answer 1

описание алгоритма: задан список А и число M, n = len(A). для того чтобы найти все возможные варианты выборки из А необходимо построить множество двоичных чисел от 1 до 2^n-1 и складывать только те индексы разряд которого которого в двоичном числе равен 1, т.е. для двоичного числа 1100 это будут индексы 2 и 3.
Если сумма будет равна М вывести последовательность индексов, иначе идем далее
Язык Python
A=[21,4,5,4,32] #Задание массива А
M = 9             #Задание М
for i in range(1, 2**len(A)-1): # для всех i от 1 до 2^n-1
  ind = []                             # список индексов используемых в данной итерации
  cnt = 0                             # сумма элементов А
  for j in range(len(A)):          # для всех j от 0 до n
    if i&2**j:                          # Если индекс есть в бинарной записи i, то
      cnt += A[j]                    # прибавить к сумме A[j]
      ind.append(str(j))                 # запомнить индекс
      if cnt > M: break            # если сумма больше M выходим из цикла
  if cnt == M:                       # если сумма равна M
    print ', '.join(ind)               # печатаем список эффективных индексов

для данной программы будет выдано две строки
1,2
2,3