主題
題目連結：
題目意譯：
給定一正整數(shù)陣列 nums。你的任務是選擇 nums 的一個子集合，將這些數(shù)字各自分別地乘上某個整數(shù)並加總。該陣列會被稱為「好的」如果你可以從陣列的任意可能之子集合和乘數(shù)而得到總和 1 之值。
回傳真（True）如果陣列是好的；反之則回傳假（False）。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [12,5,7,23]
輸出： true
解釋： 挑數(shù)字 5 和 7。
5 × 3 + 7 × (-2) = 1
範例 2：
輸入： nums = [29,6,10]
輸出： true
解釋： 挑數(shù)字 29 、 6 和 10。
29 × 1 + 6 × (-3) + 10 × (-1) = 1
範例 3：
輸入： nums = [3,6]
輸出： false
解題思維：
根據(jù)貝祖定理（Bézout's Lemma，更多資訊參見維基頁面）：
x1 、 x2 、 …… 、xn 存在 a1 、 a2 、 …… 、an 使得
a1x1 + a2x2 + …… anxn = 1
若且唯若 x1 、 x2 、 …… 、 xn 的最大公因數(shù)為 1（即互質）。
而如果已知某一數(shù)組中所有數(shù)字的最大公因數(shù)，則再新加任意數(shù)量的正整數(shù)都只會將最大公因數(shù)變小或不變。因為本題最大公因數(shù)是 1，因此如果 nums 中存在一子集合使得最大公因數(shù)為 1，則將剩下沒挑到的數(shù)字加進來（即該子集合的補集）也只會得到最大公因數(shù)為 1。
也就是說我們可以直接求整個陣列 nums 的數(shù)字之最大公因數(shù) C。如果 C ≠ 1 則不可能符合好陣列的定義，因此回傳假；反之則代表可能，因此回傳真。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
