55 组合的几种解决形式

问题描述:给定两个整数n和k，返回1...n中所有可能的k个数的组合。

回溯算法求解：由于是组合，所以所有的排列都应该从小到大进行排列，防止重复，且由于需要整合k个数，所以每个dfs的循环只能取n-k+1的范围,不然后续就去不到k个数字了，且不能比上个选取的数字大。

public numberComposition(int n,int k,List<Integer>templist,List<List<Integer>>res,int start)
{
if(k==0){list.add(templist);return;}
for(int i=start;i<=n-k+1;i++)
{
templist.add(i);
numberComposition(n,k-1,templist,res,start+1);
templist.remove(templist.size()-1);
}
}
public List<List<Integer>> NumberComposition(int n,int k)
{
List<List<Integer>>list=new LinkedList<LinkedList<Integer>>();
numberComposition(n,k,new LinkedList<Integer>(),res,1);
return res;
}