7.3  如何求正整数n所有可能的整数组合

7.3 如何求正整数n所有可能的整数组合

【出自HW面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

给定一个正整数n，求解出所有和为n的整数组合，要求组合按照递增方式展示，而且唯一。例如：4=1+1+1+1、1+1+2、1+3、2+2、4（4+0）。

分析与解答：

以数值4为例，和为4的所有的整数组合一定都小于4（1，2，3，4）。首先选择数字1，然后用递归的方法求和为3（4-1）的组合，一直递归下去直到用递归求和为0的组合的时候，所选的数字序列就是一个和为4的数字组合。然后第二次选择2，接着用递归求和为2（4-2）的组合；同理下一次选3，然后用递归求和为1（4-3）的所有组合。依此类推，直到找出所有的组合为止，实现代码如下：

程序的运行结果如下：

运行结果分析：

从上面运行结果可以看出，满足条件的组合是：{1，1，1，1}，{1，1，2}，{1，3}，{2，2}，{4}，其他的为调试信息。从打印出的信息可以看出：在求和为4的组合中，第一步选择了1；然后求3（4-1）的组合也选了1，求2（3-1）的组合的第一步也选择了1，依次类推，找出第一个组合为{1，1，1，1}。然后通过count--和i++找出最后两个数字1与1的另外一种组合2，最后三个数字的另外一种组合3；接下来用同样的方法分别选择2、3作为组合的第一个数字，就可以得到以上结果。

代码i=（count==0？1：result[count-1]）；用来保证：组合中的下一个数字一定不会小于前一个数字，从而保证了组合的递增性。如果不要求递增（例如把{1，1，2}和{2，1，1}看作两种组合），那么把上面一行代码改成i=1即可。