[Leetcode] Combination Sum III

 1 import java.util.*;
 2 
 3 public class Solution {
 4     private void DFS(List<List<Integer>> res, List<Integer> nums,int start, List<Integer> tmpres, int tmpsum, int k, int n){
 5         System.out.println(tmpres);
 6         if(tmpres.size()==k&&tmpsum==n&&start==nums.size()){
 7             System.out.println("hello");
 8             List<Integer> copyres = new LinkedList<Integer>();
 9             copyres.addAll(tmpres);
10             res.add(copyres);
11             return;
12         }
13         //if(tmpres.size()>k||tmpsum>=n||start==nums.size()) return;
14         //使用上面的条件，会出现问题，关键是当达到相等的时候，应该继续递归
15         //原因是添加结果的条件是当start==nums.size()的时候
16         if(tmpres.size()>k||tmpsum>n||start==nums.size()) return;
17 
18         //add nums[start]
19         tmpres.add(nums.get(start));
20         DFS(res,nums,start+1,tmpres,tmpsum+nums.get(start),k,n);
21         tmpres.remove(tmpres.size()-1);
22         //skip nums[start]
23         DFS(res,nums,start+1,tmpres,tmpsum,k,n);
24     }
25     public List<List<Integer>> combinationSum3(int k, int n) {
26         List<List<Integer>> res = new LinkedList<List<Integer>>();
27         List<Integer> nums = new LinkedList<Integer>();
28         for(int i=1;i<=9;i++) nums.add(i);
29         List<Integer> tmpres = new LinkedList<Integer>();
30         DFS(res,nums,0,tmpres,0,k,n);
31         return res;
32     }
33 }