iT邦幫忙

2025 iThome 鐵人賽

DAY 6
0
佛心分享-IT 人自學之術

從Leetcode到實務的橋樑系列 第 16

Day 16(LeetCode 40. Combination Sum II)

  • 分享至 

  • xImage
  •  

題目介紹:
類似於作天的Combination Sum題目的延伸題目,但每個候選數字只能使用一次,且陣列可能包含重複元素。給定一個整數陣列 candidates 和目標值 target,要求找出所有不重複的組合,使其數字和等於目標值。這題考驗回溯演算法、重複元素處理以及剪枝技巧。典型解法為排序後回溯,跳過重複元素,避免結果重複。
解題流程:
先對陣列排序,再用回溯法累加數字到目標,遇到重複元素跳過,超過目標則剪枝,找到符合組合就記錄結果。
程式碼及執行結果截圖:
https://ithelp.ithome.com.tw/upload/images/20250926/20168871gck9utF0Jr.png
學習心得:
這題與Combination Sum不同的是,每個數字只能使用一次,且陣列中可能有重複元素,因此必須先排序,並在遞迴中跳過重複數字,才能避免結果重複。這題強化了我對邊界條件的掌握,例如目標值小於候選數字時立即剪掉,以及如何控制遞迴起始索引以確保每個元素只用一次。透過這題,我學會了如何在回溯中同時考慮效率與正確性,並理解排序、剪掉和跳過重複元素在組合問題中的重要性。
延伸邏輯知識面:
1.金融與投資組合:限制每個投資標的只能選一次,設計多種組合達到收益目標。

2.活動或任務安排:每個任務或活動只安排一次,探索所有可行順序。

3.產品搭配推薦:電商系統中,組合不同商品滿足特定條件,避免重複推薦。


上一篇
Day15( 39. Combination Sum)
下一篇
Day17(這週綜合心得)
系列文
從Leetcode到實務的橋樑18
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言