/*
输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,使其和等于 m ,要求将其中所有的可能组合列出来
*/

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

int length;
void PrintSolutions(int *flag)
{
	for (int i = 0; i<length; i++)
	{
		if (flag[i] == 1)
		{
			
			cout << i + 1 << "  ";
		}
	}
	cout << endl;
}

void BagProblem(int m, int n, int *flag)
{
	if (n<1 || m<1)
		return;
	if (m < n)
		n = m;
	if (n == m)
	{
		//将n集合中值为n的元素的flag制为1
		flag[n - 1] = 1;
		PrintSolutions(flag);
		flag[n - 1] = 0;
	}
	//最高位制为1
	//F(sum,n)=F(sum-n,n-1)+F(sum,n-1);
	//n个元素凑sum等价于
	//n-1个元素凑sum-n（这部分说明原先有n参与才凑成sum）
	//和n-1个元素凑sum（这部分说明原先没有n参与也能凑成sum）
	flag[n - 1] = 1;
	BagProblem(m - n, n - 1, flag);
	flag[n - 1] = 0;
	BagProblem(m, n - 1, flag);
}

int main()
{
	int m=0, n=0;
	cout << "Please input the m and n:" << endl;
	cin >> m >> n;
	cout << "The solution is:" << endl;
	length = n;
	//创建大小为n的数组flag
	int *flag = (int *)malloc(sizeof(int)*n);
	memset(flag, 0, sizeof(flag));
	BagProblem(m, n, flag);
	free(flag);
	return 0;
}