1
$\begingroup$

This is an interview question:

Given a pile of cards, how to program to get card combinations whose sum is closest to 21?

Example:

input:

Array : 2, 3, 4, 5, J, K

output:

2, 4, 5, J

2, 4, 5, K


I have a naive solution:

check if two cards' sum is 21;

check if three cards' sum is 21;

check if four cards' sum is 21;

check if five cards' sum is 21;(Max number of cards in blackjack)

However, this is brute force solution.

Can anyone give me a hint to get a better solution? Thanks!

$\endgroup$
  • $\begingroup$ I am not a blackjack player (nor any other color), and I do not know the rules. Explain how I get cards, and what I must do with them. Do I just get 5 cards, and look if some of them add to 21. What am I supposed to program. What are the primitive moves I have available to program whatever algorithm you are asking. $\endgroup$ – babou Oct 12 '14 at 11:56
  • $\begingroup$ Why in your example there are two combinations in the output? I would have expected only "2,4,5,J", since it is closer to 21 than "2,4,5,K". Your brute force doesn't find either of these combinations, since neither sums up to 21 exactly. Can you clarify? $\endgroup$ – Juho Oct 12 '14 at 12:03
  • $\begingroup$ @Juho Sorry about confusion. Actually, it's a blackjack game. value of any cards like 10,J,Q,K is 10. Any Value of card A might be 1 or 11. My question was get combination's sum which is closest to 21. $\endgroup$ – Chris Su Oct 12 '14 at 21:55
  • $\begingroup$ @babou Sorry about confusion. BlackJack's rules: en.wikipedia.org/wiki/Blackjack. My question is "try to find k (k<=5) cards's sum is closest to 21; Output the combination" $\endgroup$ – Chris Su Oct 12 '14 at 21:58
2
$\begingroup$

You have at least two options.

If the number of cards is very small, as in your example, then you can go over all possible subsets of cards and compute their sum, taking note of the one closest to 21. Then go over all of them again and output the ones achieving the best sum. With a realistic number of cards this will be very fast.

What they might have expected you to answer is to use dynamic programming. For each sum from 2 to 21, go over all cards and see if it is achievable from an earlier sum (including 0), and if so, annotate this with all possible cards. Now find the best sum and follow the edges back to 0.

$\endgroup$
  • $\begingroup$ Yes. I think they might need dp solution. My secondary thought is use dp[i][j], which sum of j cards taken from first i cards. $\endgroup$ – Chris Su Oct 12 '14 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.