4.2　24點

題目描述（第679題）

有4張分別寫有1到9數字之一的牌，需要判斷是否能通過×、/、+、-、(，)的運算得到24。

示例1

輸入：[4,1,8,7]

輸出：True

解釋：(8-4)×(7-1)=24。

示例2

輸入：[1,2,1,2]

輸出：False

注意

除法運算符/表示實數除法，而不是整數除法，例如，4/(1-2/3)=12。

這里的每個運算符都需要對兩個數進行運算。特別是我們不能把–用作一元運算符。例如，當輸入為[1,1,1,1]時，表達式-1-1-1-1是不被允許的。也不能將數字連接在一起。例如，當輸入為[1,2,1,2]時，不能寫成12+12。

報數游戲熱身過后，讓我們來解決一道更貼近生活的題目。相信不少讀者都玩過 24點，玩游戲的時候你是否考慮過具體算法呢？

解法一　回溯遞歸法

思路

4張牌加上四則運算，為拼出24點我們需要對這些數字和運算規則進行排列組合，如示例1中，輸入數組為[4,1,8,7]，一種解法是將數字重新排列為8,4,7,1，同時先后進行（8-4）、（7-1）及兩者的乘法。由此不難看出針對此游戲，我們是可以窮舉出所有潛在結果并得到答案的，窮舉的過程可以分兩步進行。

●　計算4個數字的全排列，如果有重復數字應當去重。

●　針對每一種排列計算所有可能的結果，與24進行比對。

數字的排列組合

第1步需要得出給定4個數字可以產生的全部非重復排列。Python語言自帶的itertools模塊是實現了全排列函數的，我們可以使用它方便地得到全排列結果：[list(i)for i in itertools.permutations(nums)]。不過求排列組合實際上也是力扣（LeetCode）中的一類題目，此時的場景對應第47題全排列II問題，我們來看一看如何使用笨方法來實現全排列。

學習過排列組合的讀者應該知道，n個數字的全排列一共有n!個，其推理也并不復雜：選擇排列中的第1個數字時有n種選擇，選擇第2個數字時因為已經用掉了一個，那么還剩n– 1種選擇，以此類推，直至最后一個位置的可選數字只有一個，將所有的可能性相乘就得到了最終的結果。

如果使用計算機程序實現上述過程，最適合的算法思想是什么呢？答案是回溯法，從第1位開始逐位放入數字，得到某個排列之后，如果它不是最后一個解（或者在題目的限定條件下不是正確解），回溯算法會回到上一步做一些改變，即回溯并再次嘗試，直至覆蓋所有可能的路徑。

當存在相同數字時，全排列可能出現重復，去重可以減少不必要的計算。尋找排列前先對數字進行排序，回溯時遇到前后數字重復且前邊數字已經嘗試過的情況就跳過計算過程。當然去重并不是必需的，如果去重增加的額外計算成本高于帶來的收益的話，也可以不進行優化。

計算排列可能的結果

有了上面的全排列結果，問題便簡化成了求一組固定數字組合計算的問題。由于無法判斷計算的范圍，我們又需要對所有可能進行窮舉。那么窮舉的思路是什么呢？加/減/乘/除四則運算大家再熟悉不過了，它們的共同點在于都屬于二元運算，即作用于兩個變量的數學運算，因此除除數為0的特殊情況外，不管組合的先后順序或數值如何變化，每一步始終都是兩個變量的計算，無論變量是排列中的數字，還是其他數字計算得出的結果。

定義函數compute(self,nums: List[float])，判斷給定數組（排列）為nums時能否湊成24點，當數組中的數字多于一個時，對于數組中所有可能的相鄰數字對，兩兩結合計算出四則運算的結果，并使用得到的結果替換原排列中的這對數字來得到數組nums1（數組中的數字個數因此減1），重復compute(nums1)，直到只有一個數字時將它與24進行比較，得到結果。

對全排列中的每一種排列進行計算比較，我們便能得出是否可以得到24點。

其他注意事項

在大多數編程語言中，浮點數并不能完全精確地表示十進制數，并且即使是最簡單的數學運算也可能引起一定的誤差，比如：

因此在對計算結果進行比較時，需要考慮避免上述問題的出現，在比較24點時我們采取了下面的做法。

代碼

解法二　迭代遞歸法

思路

在上面的窮舉思路中，我們將數字排列與組合計算分成了兩個部分，這樣做更易于理解，但程序運行時將產生冗余。

一方面，基于加法和乘法的交換律，不同排列組合的計算過程可能是等價的，會產生重復的計算。另一方面，一旦正確解被找到，剩余的排列也就不需要再考慮了，并不需要繼續窮舉。

基于上述原因，我們可以考慮替換全排列的推算，將數字窮舉過程與計算過程相結合。同樣，基于相鄰數字對組合計算的方法，我們直接在原數組的基礎上進行嘗試即可。

定義函數compute(self,nums: List[int],n: int)，其中n表示當前數組中的變量個數。使用數組下標left、right指向數字對，針對每一種排列（既包含初始的4個數字的排列，也包含使用計算結果產生的新數字排列），由左向右進行兩兩組合并計算四則運算的結果。與上一解法的不同之處在于：兩數字并不需要相鄰，因為數組的排列并未固定；計算時兩數字的前后順序并不固定，這意味著減法和除法將產生兩種結果。使用與上題類似的遞歸法，可以窮舉得到最終的結果。

代碼