Dues monedes de cada (1) P62113

Donat un nombre $x$ i $n$ valors diferents de monedes $m_1$ …$m_n$, de quantes maneres es pot aconseguir canvi $x$ usant cada valor com a molt dues vegades? Considereu diferents dues monedes amb el mateix valor.

Per exemple, si $x = 4$ i disposem dels dos valors 1 i 2, llavors tenim tres maneres: $1 + 1' + 2$, $1 + 1' + 2'$, i també $2 + 2'$.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb $x$ i $n$, seguit de $m_1$ …$m_n$. Suposeu $1 \le n \le 20$, $1 \le m_i \le x \le 1000$, i que totes les $m_i$ són diferents.

Sortida

Per a cada cas, escriviu en ordre lexicogràfic totes les maneres d’aconseguir exactament canvi $x$ usant cada valor com a molt dues vegades. Escriviu cada solució amb els valors de petit a gran. A l’hora d’ordenar els valors, suposeu $1 < 1' < 2 < 2' < \dots$. Useu “1p” per escriure $1'$, etcètera. Escriviu una línia amb 10 guions al final de cada cas.

Pista

Un backtracking mitjanament espurgat hauria de ser suficient.