dfs 参考I II， 切不要K sum
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.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
public class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> res =new ArrayList<List<Integer>>(); if(k>=10||n>45||n<k) return res; dfs(k,n,res,new ArrayList<Integer>(),1); return res; } public void dfs(int k, int t,List<List<Integer>> res, ArrayList<Integer> item, int start ){ if(t==0){ if(item.size()==k){ res.add(new ArrayList<Integer>(item)); } return; } if(t<0) return; for(int i=start;i<10;i++){ item.add(i); dfs(k,t-i,res,item,i+1); item.remove(item.size()-1); } } }
原文：http://www.cnblogs.com/jiajiaxingxing/p/4532257.html