def coins_sets(list_of_coins, target_sum, cur_coin, cur_coins_set, result, remaining_sum):
if sum(cur_coins_set) > target_sum or (remaining_sum + sum(cur_coins_set)) < target_sum:
return
if sum(cur_coins_set) == target_sum:
result.add(tuple(cur_coins_set))
return
for i in range(cur_coin, len(list_of_coins)):
coins_sets(list_of_coins, target_sum, i + 1, [*cur_coins_set, list_of_coins[cur_coin]], result, remaining_sum - list_of_coins[cur_coin])
list_of_coins = [1, 1, 1, 1, 2, 3, 3, 5, 5, 5, 10, 10, 15, 20, 20, 25, 50, 50, 100]
target_sum = 25
result = set()
coins_sets(list_of_coins, target_sum, 0, [], result, sum(list_of_coins))
for cs in result:
print(cs)def find_coins_set(list_of_coins, target):
result = []
cur_sum = []
left_ind, right_ind = 0, len(list_of_coins) - 1
left_stop, right_stop = 0, len(list_of_coins) - 1
while left_ind < right_ind:
if list_of_coins[right_ind] > target:
right_ind -= 1
continue
if sum(cur_sum) + list_of_coins[right_ind] == target: cur_sum.append(list_of_coins[right_ind])
result.append(cur_sum)
right_ind -= 1
right_stop = right_ind
cur_sum = []
continue
if sum(cur_sum) + list_of_coins[left_ind] == target: cur_sum.append(list_of_coins[left_ind])
result.append(cur_sum)
left_ind += 1
left_stop = left_ind
cur_sum = []
continue
if sum(cur_sum) + list_of_coins[right_ind] < target: cur_sum.append(list_of_coins[right_ind])
right_ind -= 1
continue
if sum(cur_sum) + list_of_coins[left_ind] < target: cur_sum.append(list_of_coins[left_ind])
left_ind += 1
continue
if sum(cur_sum) + list_of_coins[right_ind] > target and right_ind < right_stop: cur_sum.delete(list_of_coins[right_ind])
right_ind += 1
continue
if sum(cur_sum) + list_of_coins[left_ind] > target and left_ind > left_stop: cur_sum.delete(list_of_coins[left_ind])
left_ind -= 1
continue
return result
list_of_coins = [1,1,2,3,3,5,5,5,10,10,15,20,20,25,50,50,100]
list_of_coins.sort()
target = 35
max_count = sum(filter(lambda x: x <= target, list_of_coins))//target
print(f'max count {max_count}')
print(find_coins_set(list_of_coins, target))