problem

輸入為一個元素皆為正整數的陣列，元素可能重複，假設每個數字代表一個硬幣的面額，回傳這些硬幣無法加總組合出的最小金額。例如陣列 [1, 2, 5]，則無法組合出的最小金額為 4；如果陣列為 []，則無法組合出的最小金額為 1。

sample input:
coins = [5, 7, 1, 1, 2, 3, 22]

sample output:
20

暴力解法是從 1 開始，檢查擁有的錢有沒有辦法加總出每個數字，但這代表每看一個數字就要看過一遍所有的錢，而且還要思考如何計算加總的過程。雖然這種方法很慢也很複雜，但不妨做為面試討論的起點，再延伸到以下比較快的解法。

另外一個想法是，因為要找的是最小的數字，所以將陣列排序，從最小的數字開始考慮。

如果觀察有序陣列 [1, 2, 4]，這些硬幣可以組合出 1, 2, 3, 4, 5, 6, 7 等金額。此時，如果再加一個面額為 9 的硬幣，會發現 8 就會是無法組合出來的最小金額，但如果加一個面額為 7 的硬幣，除了可以得到 8 之外，還可以組合出 1-14 所有金額。

也就是說，排序後的陣列如果第一個數字不是 1，不能組出的最小數字當然就是 1，否則目前可以組合出的最大數字 (sum) 為 1。

在這之後每多一個硬幣都會有兩種情況，一種是如果下一個硬幣面額 value > sum + 1，則 sum + 1 就是無法組出的金額。

另一種是，如果 value <= sum + 1，則一定可以加到 value + sum 這個金額。之所以可以肯定這點，是因為 value 可以加上前面所有已知的數字，例如 [1, 2]，可以加出 1, 2, 3，此時如果加入硬幣 4，就一定可以得到 4 + 1、4 + 2、4 + 3，所以新的 sum 就會是 7。

如果最終有將陣列遍歷完，則無法加出的最小數字是 sum + 1。

n 為陣列長度，
time: O(nlog(n)) 這個時間來自排序，嚴格來說排序後的運算會再加上 O(n) 時間，但因為 n 較小所以省略。
space: O(1) 這是原地排序的情況，面試時可以討論，如果不可以原地排序，則空間複雜度為 O(n)。

function nonConstructibleChange(coins) {
  coins.sort((a, b) => a - b);
  let sum = 0;
  for (const coin of coins) {
    if (coin > sum + 1) return sum + 1;
    sum += coin;
  }
  return sum + 1;
}

前面的邏輯在看懂前根本就跟巫術一樣，但看懂後程式碼本身就非常簡單，沒什麼懸念。不確定面試時有沒有辦法冷靜觀察出這些，但從最簡單的例子展開應該還是最保險的做法。