Coalicions polítiques P13519

La situació política d’un país llunyà està complicada. Hi ha $n$ partits polítics, numerats entre 1 i $n$, cadascun amb $d_i$ diputats. Diem que una coalició de partits és guanyadora si la suma dels nombres de diputats és almenys una certa $k$. Una coalició guanyadora és redundant si té algun partit tal que, treient-lo de la coalició, aquesta encara té $k$ o més diputats. Feu un programa que calculi totes les coalicions guanyadores no redundants.

Entrada

L’entrada consisteix en diversos casos, només amb nombres naturals, cadascun amb $k$ i $n$, seguides de les $d_i$. Suposeu $1 \le n \le 20$, i que tant $k$ com les $d_i$ estan entre 1 i $10^6$.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic totes les coalicions guanyadores no redundants. Escriviu una línia amb 10 guions després de cada cas.

Observació

La solució esperada és un backtracking amb diverses optimitzacions. Els jocs de proves s’han generat amb la intenció que els punts que us doni el jutge (sobre 100) siguin una aproximació a la nota màxima que podeu obtenir.