Leetcode 解題紀錄 698. Partition to K Equal Sum Subsets
Oct 9, 2022
題目
判斷陣列中的元素可以被分成 k 個群組，每個群組內的元素相加和必須相同，群組中的元素數目不用一樣
限制
- 陣列的元素與 k 介於 1~ 16
- 元素值 1~10000
- 每個元素出現 1~4 次
觀察
- 群組和可以透過加總全部數值再除以 k
- 原本陣列的元素總和必須能夠被 k 整除，否則無法均分到每個群組，這可以是個提早結束的條件
- 當 k = 1 的時候也可當成提早結束的條件
- 考慮過 Greedy ，但在這裡不適用，並非找到任何相加為群組和的數字就可以，例如 [1,1,2,2,3,3] k=3 可以算出群組和為 4，如果拿 [1,1,2] 將會導致剩餘數字無法組成群組
- 由於需要試所有不同的組合，backtracking 在這裡是比較適合的方法
思路
- 使用 recurisve function 來進行所有組合的遍覽
- k 個群組的資料結構的決定是這個程式的重點，由於題目並沒有要求要把群組的所有元素回傳，可以簡化成有 k 個整數的陣列，每個數字視為一 個群組
- 每個陣列初始為群組和，每當放進一個元素時，就從和裡減掉這個數字，一直到 0 ，代表這個群組的元素已經都找到，而當陣列中的所有數字都變成 0 的時候就是成功了
Trial 1
- 遞迴參數為陣列，目前數字的指標以及各個群組目前的和
- 每次遞迴先取出目前指標的數字，試著放入每個可以容納的群組，移動指標並遞回到下一層
- 停止條件為指標到達陣列結尾，這時檢查每個群組是否都為 0 ，如果是則返回成功，不是的話返回失敗
- 在遞迴回傳失敗時，必須把放入群組的數拿出來，好放入下個群組進行下一個遞迴
結果是 TLE，因為每個數字都會產生 k 次的遞迴，時間複雜度大約是 k 的 n 次方
Trial 2
- 從第一次的遞迴可以觀察到，當每個群組的初始值一樣時，放入第一個群組與第二個的結果會是一樣的，因此相同數值的群組就不需要遞迴下去了
- 利用一個集合來紀錄已經遞迴過的群組數值
經過這樣的改善後，通過了所有 TC，但結果不夠好
Trial 3
經過參考別人的解法，發現大家都會先排序，因此試著將陣列中的元素進行排序
經過排序後，結果進步了不少，這是只要找到一次成功的 case 就可以結束的問題，資料的位置影響很明顯
