Enumeration — 列舉法
Published in
Dec 8, 2021
列舉法又稱為窮舉法，簡單來說就是把所有可能發生的狀況都列出來，再根據問題提供的條件，從中找出符合條件的解答，也就是所謂的暴力破解法，優點是簡單直觀，缺點就是當問題的範圍很廣，執行時間會等比上升，因此不適合拿來解範圍過於廣泛的題目。
舉一項生活中的實例，小學的時候都會玩的交換日記，上面會有一個金屬扣搭配一個密碼鎖的鎖頭(如果不知道這是甚麼東西的人，代表我們之間有世代的隔閡😢)，防止有人想偷看裡面的內容，只有交換日記的當事人才知道密碼是多少，但一定會有那種調皮的同學會想偷看裡面寫甚麼，趁沒人注意的時候把所有的密碼都嘗試過一遍，想在這些密碼的排列組合中找出正確的密碼，這就是列舉法的一種。
雞兔同籠
這是中國古代經典的數學題目，也可以用列舉法來推算答案，假設有數隻雞和兔子被關在同一個籠子裡，從上面數有35顆頭，從下面數有94隻腳，試問籠子裡有幾隻兔子和幾隻雞?
用js實作:
大致理解列舉法的思維之後，我們就用Enumeration的標籤從leetcode中挑一題1534. Count Good Triplets 來說明列舉法吧，題目會給予一個陣列以及三個整數a、 b、 c ，要你從陣列當中找出有幾組符合條件的三胞胎(這邊的三胞胎指的是三個一組) ，每組三胞胎 (arr[i], arr[j], arr[k]) 會具備以下的條件:
0 <= i < j < k < arr.length|arr[i] - arr[j]| <= a|arr[j] - arr[k]| <= b|arr[i] - arr[k]| <= c
|x| 代表是取x的絕對值.
leetcode提供的example如下:
Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].用js實作:
