LeetCode：组合总数III【216】

题目描述

找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。

说明：

• 所有数字都是正整数。
• 解集不能包含重复的组合。 

示例 1:

输入: k = 3, n = 7输出: [[1,2,4]]

示例 2:

输入: k = 3, n = 9输出: [[1,2,6], [1,3,5], [2,3,4]]

题目分析

　　采用递归回溯框架解题即可。

Java题解

class Solution {      public List
     
      
       > combinationSum3(int k, int n) {        List
       
        
         > ans =  new ArrayList<>();        backtrack(ans,new ArrayList<>(),k,n,0,0,1);        return ans;    }    public void backtrack(List
         
          
           > list,List
           
             tmpList,int k,int n,int curk,int curn,int num) { if(curn>n||curk>k) return; if(curk==k&&curn==n) list.add(new ArrayList<>(tmpList)); else{ for(int i=num;i<10;i++) { tmpList.add(i); backtrack(list,tmpList,k,n,curk+1,curn+i,i+1); tmpList.remove(tmpList.size()-1); } } }}