DeepSeek LeetCode 216. 组合总和 III Java实现

LeetCode 216. 组合总和 III - Java 实现题目描述找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数且每种组合中不存在重复的数字。解题思路使用回溯DFS从 1 到 9 依次选择数字剪枝条件· 已选数字个数超过 k → 剪枝· 当前和已超过 n → 剪枝· 剩余可选的数字个数不够凑齐 k 个 → 剪枝代码实现importjava.util.ArrayList;importjava.util.List;classSolution{publicListListIntegercombinationSum3(intk,intn){ListListIntegerresnewArrayList();backtrack(res,newArrayList(),k,n,1);returnres;}privatevoidbacktrack(ListListIntegerres,ListIntegerpath,intk,intremain,intstart){// 找到满足条件的组合if(path.size()kremain0){res.add(newArrayList(path));return;}// 剪枝元素个数超过 k或剩余和小于 0if(path.size()k||remain0){return;}for(intistart;i9;i){// 剪枝当前数字已经大于剩余需要的和if(iremain)break;path.add(i);backtrack(res,path,k,remain-i,i1);path.remove(path.size()-1);}}}剪枝优化版classSolution{publicListListIntegercombinationSum3(intk,intn){ListListIntegerresnewArrayList();backtrack(res,newArrayList(),k,n,1);returnres;}privatevoidbacktrack(ListListIntegerres,ListIntegerpath,intk,intremain,intstart){if(path.size()k){if(remain0)res.add(newArrayList(path));return;}// 剪枝剩余可选的数字不足以凑齐 k 个// 从 start 到 9 一共有 (9 - start 1) 个数字可选// 还需要选 (k - path.size()) 个数字for(intistart;i9-(k-path.size())1;i){if(iremain)break;// 再选更大的数肯定超过 remainpath.add(i);backtrack(res,path,k,remain-i,i1);path.remove(path.size()-1);}}}复杂度分析指标 复杂度时间复杂度 O(C(9, k) × k)最多枚举 C(9, k) 种组合空间复杂度 O(k)递归栈深度关键点start 参数保证组合不重复、不遗漏每次从 i 1 继续选择remain 参数用减法代替传递 sum简化逻辑剪枝技巧· i remain 时直接 break后面的数更大· i 9 - (k - path.size()) 1确保剩余数字够凑 k 个示例输入k 3, n 7输出[[1,2,4]]输入k 3, n 9输出[[1,2,6],[1,3,5],[2,3,4]]