cards.ts

type Card = number;

function matches(card: Card, cs: readonly Card[]): boolean {
	function attempt(cs: readonly Card[], partialSum: number, unused: readonly Card[]): boolean {
		let noGood = [...unused];
		let toTry: Card[] = [...cs];

		for (let next = toTry.pop(); next !== undefined; next = toTry.pop()) {
			if (next === card) {
				continue; // cards that are equal are always okay
			} else if (next > card) {
				return false; // there is an unmatchable card, fail the whole thing
			} else {
				let sum = partialSum + next;
				if (sum === card) {
					// could be part of a valid solution, we have a capturing set 
					// that equals the card
					// put all the no-good cards back into the set to try
					if (go([...toTry, ...noGood], 0, [])) {
						return true;
					}
				} else if (sum < card) {
					// could be part of a valid solution,  we have a capturing set 
					// that does not yet equal the card
					// keep matching with the current sum & no-good set
					if (go(toTry, sum, noGood)) {
						return true;
					}
				}

				// otherwise put it into the no-good set
				// we will try again later
				noGood.push(next);
			}
		}

		// run out of cards to try, we have suceeded if 
		// there's nothing left to check
		return noGood.length === 0 && partialSum === 0;
	}

	const cache = new Map<string, boolean>();
	function go(cs: readonly Card[], partialSum: number, unused: readonly Card[]): boolean {
		const key = `${[...cs].sort().join()}|${partialSum}|${[...unused].sort().join()}`;
		const cached = cache.get(key);
		if (cached !== undefined) {
			return cached;
		}

		const result = attempt(cs, partialSum, unused);
		cache.set(key, result);
		return result;
	};

	return go(cs, 0, []);
}

const examples = [
	[10, [10, 10]],
 	[10, [10, 5, 5]],
  	[10, [10, 2, 8]],
  	[10, [2, 8, 6, 2]],
  	[5,  [10]],
  	[5,  [2, 2, 2, 2, 2]],
  	[5, [10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10]],
  	[5, [5, 5, 5, 5, 5, 5]],
	[10, [9, 9, 1, 1]],
	[10, [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
	      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
	[10, [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
	      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
	[10, [9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9,
	      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
	[10, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
	[10, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
	[10, [8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
		  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	      1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],
	[10, [8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9,
		  2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1]],
	[10, [8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9,
		  2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]],
	[10, [8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9, 8, 9,
		  2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2]],
] as const;

for (const [card, cards] of examples) {
	console.log(`${card} matches ${cards}: ${matches(card, cards)}`);
}