[Amazon Question][LeetCode] 24 Game

Problem: You have 4 cards each containing a number from 1 to 9. You need to judge whether they could operated through *, /, +, -, (, ) to get the value of 24.

Example:

Input: [4, 1, 8, 7]
Output: True
Explanation: (8-4) * (7-1) = 24

Input: [1, 2, 1, 2]
Output: False

Note:

1. The division operator / represents real division, not integer division. For example, 4 / (1 - 2/3) = 12.
2. Every operation done is between two numbers. In particular, we cannot use - as a unary operator. For example, with [1, 1, 1, 1] as input, the expression -1 - 1 - 1 - 1 is not allowed.
3. You cannot concatenate numbers together. For example, if the input is [1, 2, 1, 2], we cannot write this as 12 + 12.

Approach: This problem is kind of backtracking / DFS problem where we need to try every combination and see if it is giving the desired result or not. If not then we return false otherwise true.

Given that we can apply '( and ')', we just don't need to care about the sequence. Basically we take two cards and then replace these cards with all the possible results one by one in the array and see if we can get the value 24 so you see at every step we are reducing the number of cards by 1. Hence our decision condition / end of recursion condition will be when cards just have length 1. When we have only one card, we can check if the card is equal to 24 or not and return accordingly.

The possible results of two cards c1 and c2 could be:

1. c1 + c2
2. c1 - c2
3. c2 - c1
4. c1 * c2
5. c1 / c2 here c2 must not be 0
6. c2 / c1 here c1 must not be 0

Please also note that '/' is floating point operator here so at the final check we should consider some div error like .001 or .0001.

Implementation in C#:

        public static bool JudgePoint24(int[] nums)

        {

            List<double> cards = new List<double>();

            foreach (int num in nums)

            {

                cards.Add((double)num);

            }

            return CanGetValue(cards);

        }

        private static bool CanGetValue(List<double> cards)

        {

            int len = cards.Count;

            if (len == 1)

            {

                return Math.Abs(cards[0] - 24) < 1e-2;

            }

            for (int i = 0; i < len; ++i)

            {

                double card1 = cards[i];

                for (int j = i + 1; j < len; ++j)

                {

                    double card2 = cards[j];

                    List<double> possibleResults = new List<double> { card1 + card2, card1 - card2, card2 - card1, card1 * card2 };

                    if (card1 != 0)

                    {

                        possibleResults.Add(card2 / card1);

                    }

                    if (card2 != 0)

                    {

                        possibleResults.Add(card1 / card2);

                    }

                    List<double> nextCards = new List<double>();

                    for (int k = 0; k < len; ++k)

                    {

                        if (k == i || k == j)

                        {

                            continue;

                        }

                        nextCards.Add(cards[k]);

                    }

                    foreach (double result in possibleResults)

                    {

                        nextCards.Add(result);

                        if (CanGetValue(nextCards))

                        {

                            return true;

                        }

                        nextCards.RemoveAt(nextCards.Count - 1);

                    }

                }

            }

            return false;

        }

Complexity: O(1) as you see there will be at max 4C2 * 4 * 3C2 * 4 * 2C2 * 4  = 12 * 4 * 6 * 4 * 2 * 4 = 9216 iterations. However if we want to generalize it, It will be:

nC2 * 4 * (n-1)C2 * 4 * (n-2)C2 * 4....2C2 * 4

= 4*(n-1)* ( n*(n-1) * (n-1)*(n-2) * (n-2)*(n-3) *....*2)

= 4 * (n - 1) * ((n * (n - 1) * (n -2) * (n - 3)...* 2) * ((n - 1) * (n - 2) * (n - 3) * ... * 2)))

 = 4 * (n - 1) * (!n * !n-1)

= O(n * !n * !n -1)