【题目】

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.

Note:

• • All numbers will be positive integers.
  • The solution set must not contain duplicate combinations.

Example 1:

Input: k = 3, n = 7Output: [[1,2,4]]

Example 2:

Input: k = 3, n = 9Output: [[1,2,6], [1,3,5], [2,3,4]]

【思路】

回溯，有模板。

适用范围：需要返回点的集合，形如List<List<Integer>>。

思路：新建fun函数迭代，从一个点flag开始迭代到边界点。

List<List<Integer>> ans=new ArrayList<>();

        List<Integer> tmp=new ArrayList<>();

对于ans：当tmp满足题目要求，把tmp中的答案作为集合加入到ans中。

对于tmp：tmp中临时存储每次迭代的答案集合，每完成一次回溯，tmp.remove(tmp.size()-1)保证新一次循环时，tmp为空。

for循环flag到end，flag是已经遍历到的数据，end是遍历的终点（目标）。

反复迭代fun(ans,tmp,i+1,k,n-i);//距离期望还差n-i

【相关题目】

1、Leetcode 78]求子集 Subset 

2、Leetcode 90]求含有重复数的子集 Subset II 

3、讲解在这： 

4、

 

【代码】

class Solution {    public List
     
      
       > combinationSum3(int k, int n) {        List
       
        
         > ans=new ArrayList<>();        List
         
           tmp=new ArrayList<>();        fun(ans,tmp,1,k,n);        return ans;    }    public void fun(List
          
           
            > ans,List
            
              tmp,int flag,int k,int n){ if(tmp.size()==k&&n==0) ans.add(new ArrayList
             
              (tmp)); for(int i=flag;i<=9;i++){ tmp.add(i); fun(ans,tmp,i+1,k,n-i); tmp.remove(tmp.size()-1); } }}