> 文档中心 > Leetcode216:组合综合III

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();      }         }}

铁三角麦克风旗舰店