подпоследовательности из списка, который добавляет до 21

Question

Использование Python, как бы я идти о возвращении подпоследовательность список положительных целых чисел, которые добавляют до 21.

, например, для списка:

x = [5, 6, 7, 10, 11] 

подпоследовательности будет:

[[5, 6, 10], [10, 11]] 

Любая помощь будет оценена.

Answer 1

Вы можете сделать это с помощью Backtracking, чтобы генерировать все возможные случаи, хотя сложность была бы высокой для большого количества элементов i.e O(2^n) для n элементов в списке.

В каждом индексе рекурсивного вызова мы можем либо выбрать текущий элемент, либо выбрать его игнорировать, тем самым пройдя все возможные случаи. Код

Python:

list = [5, 6, 7, 10, 11] 

def solve(index, sum, ans): 
    if(index == len(list)): 
     if(sum == 21): 
      print(*ans) 
    else: 
     ans.append(list[index]) 
     solve(index+1, sum+list[index], ans) 
     ans.pop(-1) 
     solve(index+1, sum, ans) 

ans = [] 
solve(0, 0, ans) 

Ссылка на решение на Ideone: http://ideone.com/P5HnfU