Leetcode216:组合综合III
Leetcode216:组合综合III
-
题目:
-
找出所有相加之和为 n 的 k 个数的组合,且满足下列条件:
-
只使用数字1到9 每个数字 最多使用一次 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次,组合可以以任何顺序返回。
-
思路:回溯算法
-
代码如下:
class Solution {//定义全局变量收集结果集 List<List> result = new ArrayList(); //定义全局变量记录当前路径LinkedList path = new LinkedList(); public List<List> combinationSum3(int k, int n) { //回溯算法 backTracking(n,k,1,0); return result; } public void backTracking(int targetSum,int k,int startIndex,int sum){ //如果当前和大于目标和,直接退出(剪枝) if(sum>targetSum){ return; } //当前的路径个数符合要求,进入判断 if(path.size()==k){ //当前和符合目标和,结果集收集符合要求的节点 if(sum==targetSum){ result.add(new ArrayList(path)); return; } } //回溯核心算法 for(int i = startIndex; i<= 9-(k-path.size())+1; i++){ path.add(i); sum += i; backTracking(targetSum,k,i+1,sum); sum -= i; path.removeLast(); } }}