| ?? 算法題 ?? |
?? 算法刷題專欄 | 面試必備算法 | 面試高頻算法 ??
?? 越難的東西,越要努力堅持，因為它具有很高的價值，算法就是這樣?
?? 作者簡介：碩風(fēng)和煒，CSDN-Java領(lǐng)域優(yōu)質(zhì)創(chuàng)作者??，保研|國家獎學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗分享|好用的網(wǎng)站工具分享??????
?? 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧??
?? 人生如棋，我愿為卒，行動雖慢，可誰曾見我后退一步？????
| ?? 算法題 ?? |
?? 題目鏈接
- 216. 組合總和 III
? 題目描述
找出所有相加之和為 n 的 k 個數(shù)的組合，且滿足下列條件：
只使用數(shù)字1到9
每個數(shù)字 最多使用一次
返回 所有可能的有效組合的列表 。該列表不能包含相同的組合兩次，組合可以以任何順序返回。
示例 1:
輸入: k = 3, n = 7
輸出: [[1,2,4]]
解釋:
1 + 2 + 4 = 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,9]范圍內(nèi)使用4個不同的數(shù)字，我們可以得到的最小和是1+2+3+4 = 10，因為10 > 1，沒有有效的組合。
提示:
2 <= k <= 9
1 <= n <= 60
?? 求解思路&實現(xiàn)代碼&運行結(jié)果
? 遞歸
?? 求解思路
- 該題目通過遞歸來求解，在1到9的數(shù)字中，找到k個可以組成n的不同結(jié)果的形式返回。注意，數(shù)組中的元素最多可以選擇一次。
- 有了基本的思路，接下來我們就來通過代碼來實現(xiàn)一下。
?? 實現(xiàn)代碼
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum3(int k, int n) {
dfs(1, k, n);
return ans;
}
public void dfs(int index, int k, int n) {
if (index > 10 || k < 0 || n < 0) {
return;
}
if (k == 0 && n == 0) {
ans.add(new ArrayList<>(list));
}
for (int i = index; i < 10; i++) {
list.add(i);
dfs(i + 1, k - 1, n - i);
list.remove(list.size() - 1);
}
}
}
?? 運行結(jié)果
?? 共勉
| 最后，我想和大家分享一句一直激勵我的座右銘，希望可以與大家共勉！ |
文章來源：http://www.zghlxwxcb.cn/news/detail-857988.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-857988.html
到了這里，關(guān)于【LeetCode:216. 組合總和 III + 遞歸】的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
