求整数1-N范围和为N的所有组合

看到的一道题，给出答案

问题：找出整数1~N范围和为N的所有集合，集合里的数不允许重复。

解答：递归吧

代码如下：

#include "stdafx.h"
#include <iostream>
using namespace std;

void PrintResult(int *log,int index)
{
	for (int i = 0; i <index; ++i)
	{
		cout<<log[i]<<" ";
	}
	cout<<endl;
}

void CalCombination(int* log,int startNum,int N,int &index)
{
	if (N==0)
	{
		PrintResult(log,index);
	}

	else
	{
		for (int i = startNum; i <= N; ++i)
		{
			log[index++]=i;
			CalCombination(log,i+1,N-i,index);
		}
	}
	index--;
}

int _tmain(int argc, _TCHAR* argv[])
{
	cout<<"请输入N:";
	int N=20;
	cin>>N;
	int *log=new int[N];
	int index=0;
	CalCombination(log,1,N,index);
}

要是允许重复，也简单，将递归中的这句话改为：

CalCombination(log,i,N-i,index);

同理，还可以解决类似给定一个数组，让求和为N的元素组合，只需要现将元素排个序，然后思路相同。