題目連結:
題目意譯:
給定一個候選數字之集合 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]
]
解題思維:
因為本題每個數字只能使用一次,於是便從換零錢問題變成了類似
這題的問題。
而我們可以按照類似於
昨天的題目的方式回溯求得全部所求的組合。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。