从1-9中取k个数和为n，且数不重复。
首先可能想到的是用一个boolean数组记录用过的数字，Boolean数组的下标+1即为数字。但这题我们发现，选取的数组是递增的，所以无需使用一个数组记录使用过的数字，我们取一个数然后往后枚举即可，当满足条件时，将当前的答案记录到集合中即可。
public class Solution { public List<List<Integer>> ans = new ArrayList<>(); public List<Integer> tmp = new ArrayList<>(); /** * * @param index 当前的数字 * @param k 选k个数 * @param target 所要求的和 * @param sum 目前已经得到的和 * @param tmp 临时存储 */ public void robot(int index , int k , int target,int sum,List<Integer> tmp){ //满足条件 加入答案集 if(target == sum && k==0){ ans.add(new ArrayList<>(tmp)); return; //不满足条件 跳出 }else if(sum>target || k<0) return; //index 表示当前的数字 for(int i=index; i <= 9;i++){ //加上当前的数字 tmp.add(i); //往后移动一位 sum加上当前的数字 可选取的数量k-1 robot(i+1,k-1,target,sum+i,tmp); //还原 tmp.remove(tmp.size()-1); } } public List<List<Integer>> combinationSum3(int k, int n) { ans.clear(); robot(1,k,n,0,tmp); return ans; } }