主題
題目連結(jié)：
題目意譯：
你被給定一個由正整數(shù)所組成的陣列 nums 以及一整數(shù) k。
將陣列分割成兩個有序的群體使得每一個元素恰好只屬於其中一個群體。如果某一個群體中的元素總和大於等於 k，則該分割將稱為「好分割」。
回傳相異的好分割之方法數(shù)。由於答案可能太大，將其模 10 ^ 9 + 7 後再回傳。
如果在兩個分割之中存在某個元素 nums[i] 在兩分割中各屬於不同的群體，則兩個分割將視為相異。
限制：
1 ≦ nums.length, k ≦ 1000
1 ≦ nums[i] ≦ 10 ^ 9
範例測資：
範例 1：
輸入： nums = [1,2,3,4], k = 4
輸出： 6
解釋： 好分割為 ([1,2,3], [4]) 、 ([1,3], [2,4]) 、 ([1,4], [2,3]) 、 ([2,3], [1,4]) 、 ([2,4], [1,3]) 和 ([4], [1,2,3])。
範例 2：
輸入： nums = [3,3,3], k = 4
輸出： 0
解釋： 此陣列沒有好分割。
範例 3：
輸入： nums = [6,6], k = 2
輸出： 2
解釋： 我們可以將 nums[0] 放到第一個或是第二個群體之中。
好分割將會是 ([6], [6]) 和 ([6], [6])。
解題思維：
首先如果 nums 中所有數(shù)字的總和小於 2k，則代表不可能有好分割。因此直接回傳 0 即可。
接著可以看到算「反面」的問題比較簡單一點，也就是說我們可以先求出其中一個群體總和小於等於 k 的組合方法數(shù)。而這個其實就是換硬幣問題的變體（如這題）。
而求出其中一個群體總和值為 1 ～ k - 1 各自的方法數(shù)後（設(shè)這些方法數(shù)總和為 C），則「正面」的答案（即本題所求）為
2 ^ n - C - 2
其中 n 為 nums 之長度，而結(jié)尾的「- 2」是為了將只把所有數(shù)字集中在單一群體上的組合（題目敘述本身沒有提及兩個群體一定要非空，但是範例測資顯示了應為如此）。
而 2 ^ n 不一定要使用快速冪來計算，也可以直接包在求組合方法數(shù)的迴圈裡面。剩下的就是記得所有運算的結(jié)果都要模 10 ^ 9 + 7 以免溢位。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
