主題

LeetCode - 40. Combination Sum II 解題心得

Not In My Back Yard | 2021-04-27 00:00:12 | 巴幣 0 | 人氣 42

題目連結:


題目意譯:
給定一個候選數字之集合 candidates 以及一個目標數字 target,找到所有 candidates 中的相異組合,其中每個組合內的候選數字總和為 target。

每個 candidates 中的數字僅可以被使用一次於組合中。

注:答案集合不應包含任何重複的組合。

限制:
1 ≦ candidates.length ≦ 100
1 ≦ candidates[i] ≦ 50
1 ≦ target ≦ 30



範例測資:
範例 1:
輸入: candidates = [10,1,2,7,6,1,5], target = 8
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

範例 2:
輸入: candidates = [2,5,2,1,2], target = 5
輸出:
[
[1,2,2],
[5]
]


解題思維:
因為本題每個數字只能使用一次,於是便從換零錢問題變成了類似這題的問題。

而我們可以按照類似於昨天的題目的方式回溯求得全部所求的組合。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作