【微软谷歌面试100题--【21】从1-n中找出和为m的所有组合
第21题：
输入两个整数n 和m，从数列1，2，3.......n 中随意取几个数,使其和等于m ,要求将其中所有的可能组合列出来.
看到这样的题目，我蒙圈了，不知道从何处下手。通过在网上搜集资料，自己终于搞定了。
先看下思路：
给定了n和m;
1.要判断n*(n+1)/2与m的关系如果n*(n+1)/2>m 有戏，我们可以继续往下做，
如果n*(n+1)/2<m 没戏了，因为1,2,...n所有的数加起来还没有m大呢。所以直接退出。
2.然后就是循环找数咯循环的起始条件肯定是从 i=1开始，但是到哪里结束呢？ 循环的条件是：i<n&&i<m/2 ，这个地方就是重点了，i<n 是肯定的要有的，关键是后面 i<m/2;因为如果i >=m/2 ,那么比 i大的数在与i求和，肯定就大与m了。
3.递归求解代码：
public class Algorithm21_0 {static void getAllComp(int n,int m){String pre = m+"=";int theMax = (1+n)*n/2;if(theMax<m){System.out.println("不存在该数！");}else{for(int i=1;i<n&&i<=m/2;i++){//从1开始计数，打印出两个数的组合，并且两数不相等if(i != m-i&&((m-i)<=n)){System.out.println("here:"+pre+i+"+"+(m-i));//continue;}//调用递归，继续求得大于2个数的组合getTheResult(m-i,pre+i,i,n);}}}//调用递归，继续求得大于2个数的组合,j为组合中已用过的数，所以取大于该数的。static void getTheResult(int m,String pre,int j,int n){for(int i=j+1;i<n&&i<=m/2;i++){if(i != m-i&&((m-i)<=n))System.out.println("fuck:"+pre+"+"+i+"+"+(m-i));getTheResult(m-i,pre+"+"+i,i,n);}}public static void main(String[] args) {getAllComp(10,11);}}