主題

LeetCode - 216. Combination Sum III 解題心得

Not In My Back Yard | 2021-04-30 00:00:11 | 巴幣 0 | 人氣 29

題目連結:


題目意譯:
找到所有合法的 k 個數字之組合,其總和為 n 且符合以下情況:
只使用數字 1 到 9。
每個數字最多使用一次。

回傳一個所有可能的組合之列表。列表不得包含同樣的組合,且組合與組合之間可以任意順序排列並回傳。

限制:
2 ≦ k ≦ 9
1 ≦ n ≦ 60



範例測資:
範例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 7 = 7
不存在其他合法組合。

範例 2:
輸入: k = 3, n = 9
輸出: [[1,2,6],[1,3,5],[2,3,4]]
解釋:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
不存在其他合法組合。

範例 3:
輸入: k = 4, n = 1
輸出: []
解釋: 不存在任何合法組合。[1,2,1] 不合法,因為 1 使用了兩次。

範例 4:
輸入: k = 3, n = 2
輸出: []
解釋: 不存在任何合法組合。

範例 5:
輸入: k = 9, n = 45
輸出: [[1,2,3,4,5,6,7,8,9]]
解釋:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
不存在其他合法組合。


解題思維:
因為只會出現數字 1 ~ 9,而且每個數字最多只會出現一次。因此所有可能的選擇組合為 2 ^ 9 = 512 種。

而我們可以利用 0 ~ 511 的二進位制去表示組合。例如十進位的 51 其二進位為 000110011,而我們可以解讀成選擇 1 、 2 、 5 、 6 (二進位最右邊代表數字 1 、最左邊代表數字 9)之組合。

因此我們就窮舉(甚至可以預先建表)出 0 ~ 511 這 512 個數字的二進位表示法,並找出其中有 k 個 1 的二進位數字(代表選了恰好 k 個數字)。然後對於那些二進位數字所表示的數字組合,將每個組合求總看看是不是等於 target。如果是就將該組合放入答案陣列 answer 裡。

最後的陣列 answer 即為所求之列表。




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

創作回應

更多創作