主題

LeetCode - 39. Combination Sum 解題心得

Not In My Back Yard | 2021-04-26 00:00:07 | 巴幣 0 | 人氣 40

題目連結:


題目意譯:
給定一個相異整數之陣列 candidates 以及一個目標整數 target,回傳一個包含所有相異 candidates 之組合之列表,其中每個組合中的數字總和為 target。你可以任意順序回傳組合之列表。

candidate 同一個數字可以被無限次地選入。如果至少存在一個數字之出現頻率不同,則兩個組合相異。

保證給定的輸入中組合數字和為 target 之此種組合總數小於 150 個。

限制:
1 ≦ candidates.length ≦ 30
1 ≦ candidates[i] ≦ 200
cadidates 中所有元素相異。
1 ≦ target ≦ 500



範例測資:
範例 1:
輸入: candidates = [2,3,6,7], target = 7
輸出: [[2,2,3],[7]]
解釋:
2 、 3 為候選數字,且 2 + 2 + 3  = 7。注意 2 可以使用多次。
7 為一個候選數字,且 7 = 7。
因此只有兩種組合。

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

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

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

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


解題思維:
將 candidates 的數字們視為金錢的面額,本題便成為了典型的換零錢問題(如這題)。

不過本題需要求得數字的「組合」,因此我們需要藉由動態規劃(Dynamic Programming,DP)所得的陣列 D[i][j](代表在有前 i 種貨幣下,是否可以湊得 j 元)回溯(Backtrack)。

其回溯法本質就是深度優先搜尋(Depth First Search,DFS),藉由 DP 的遞迴式,D[i][j] =
當 j ≧ candidates[i],其為 min(D[i - 1][j - candidates[i]], D[i - 1][j]);
否則,其為 D[i - 1][j];
初始條件為 D[0][0] = true。

因此我們從 D[candidate.length][target] 開始遞迴,每次將看當前 D[i][j] 之值。為假或 (i, j) 超出範圍則回到上一層;為真的話,就遞迴看看 D[i - 1][j](不再使用 candidates[i])或是 D[i - 1][j - candidates[i]](使用一次 candidates[i])看是否可行。

當遞迴抵達初始條件 D[0][0] 時,代表我們便找到了一個組合(遞迴過程中記錄目前使用的數字)和為 target。不過根據回溯法的實作方式不同,有可能會碰到重複的組合,需要額外處理。

回溯完後即可得到所求之組合(們)。




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

創作回應

更多創作