主題
題目連結(jié)：
題目意譯：
找到所有合法的 k 個數(shù)字之組合，其總和為 n 且符合以下情況：
只使用數(shù)字 1 到 9。
每個數(shù)字最多使用一次。
回傳一個所有可能的組合之列表。列表不得包含同樣的組合，且組合與組合之間可以任意順序排列並回傳。
限制：
2 ≦ k ≦ 9
1 ≦ n ≦ 60
範(fàn)例測資：
範(fàn)例 1：
輸入： k = 3, n = 7
輸出： [[1,2,4]]
解釋：
1 + 2 + 7 = 7
不存在其他合法組合。
範(fàn)例 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
不存在其他合法組合。
範(fàn)例 3：
輸入： k = 4, n = 1
輸出： []
解釋： 不存在任何合法組合。[1,2,1] 不合法，因?yàn)?1 使用了兩次。
範(fàn)例 4：
輸入： k = 3, n = 2
輸出： []
解釋： 不存在任何合法組合。
範(fàn)例 5：
輸入： k = 9, n = 45
輸出： [[1,2,3,4,5,6,7,8,9]]
解釋：
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
不存在其他合法組合。
解題思維：
因?yàn)橹粫霈F(xiàn)數(shù)字 1 ～ 9，而且每個數(shù)字最多只會出現(xiàn)一次。因此所有可能的選擇組合為 2 ^ 9 = 512 種。
而我們可以利用 0 ～ 511 的二進(jìn)位制去表示組合。例如十進(jìn)位的 51 其二進(jìn)位為 000110011，而我們可以解讀成選擇 1 、 2 、 5 、 6 （二進(jìn)位最右邊代表數(shù)字 1 、最左邊代表數(shù)字 9）之組合。
因此我們就窮舉（甚至可以預(yù)先建表）出 0 ～ 511 這 512 個數(shù)字的二進(jìn)位表示法，並找出其中有 k 個 1 的二進(jìn)位數(shù)字（代表選了恰好 k 個數(shù)字）。然後對於那些二進(jìn)位數(shù)字所表示的數(shù)字組合，將每個組合求總看看是不是等於 target。如果是就將該組合放入答案陣列 answer 裡。
最後的陣列 answer 即為所求之列表。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
