/*
Name: 将整数n分成k份(回溯)
Copyright:
Author: 巧若拙
Date: 16/12/18 13:25
Description: 将整数n分成k份
将整数n分成k份，且每份不能为空，任意两份不能相同(不考虑顺序)。
例如:n=7，k=3，下面三种分法被认为是相同的。
1,1,5; 1,5,1; 5,1,1;
问有多少种不同的分法。
算法1：回溯算法框架1：先处理递归出口（即终点），再枚举各种可能值，递归搜索下一层。
算法2：回溯算法框架2：先枚举各种可能值，再判断是否到达终点，若到达终点则输出结果，否则递归搜索下一层。
算法2的搜索深度比算法1要少一层，但是不如算法1结构清晰。
算法3：非递归算法：自定义栈模拟算法2的递归过程。
*/
#include<iostream>
#include<cmath>
using namespace std;
const int N = 10; //整数n范围
int a[N+1] = {1}; //确保a[1]不小于1
int s = 0;
void Print(int t);
void dfs1(int n, int k, int t); //框架1
void dfs2(int n, int k, int t); //框架2
void dfs3(int n, int k); //非递归算法
int main()
{
int n, k;
cin >> n >> k;
//dfs1(n, k, 1);
//dfs2(n, k, 1);
dfs3(n, k);
cout << s << endl;
return 0;
}
void Print(int t)
{
for (int i=1; i<t; i++)
{
cout << a[i] << "+";
}
cout << a[t] << endl;
}
void dfs1(int n, int k, int t) //框架1
{
if (t == k) //到达终点，输出结果
{
a[t] = n;
Print(t);
s++;
}
else
{
for (int i=a[t-1]; i<=n/(k-t+1); i++) //枚举各种可能值，生成一个非递减序列
{
a[t] = i;
dfs1(n-i, k, t+1); //搜索下一层
}
}
}
void dfs2(int n, int k, int t)//框架2
{
for (int i=a[t-1]; i<=n/(k-t+1); i++) //枚举各种可能值，生成一个非递减序列
{
if (t == k) //到达终点，输出结果
{
a[t] = n;
Print(t);
s++;
break;
}
else
{
a[t] = i;
dfs2(n-i, k, t+1); //搜索下一层
}
}
}
void dfs3(int n, int k) //非递归算法
{
int t = 1;
while (t >= 1)
{
while (++a[t] <= n/(k-t+1)) //枚举各种可能值，生成一个非递减序列
{
if (a[t] >= a[t-1]) //满足条件
{
if (t == k) //到达终点，输出结果
{
a[t] = n;
Print(t);
s++;
break;
}
else
{
n -= a[t]; //修改标记
t++; //搜索下一层
}
}
}
a[t--] = 0; //回溯
n += a[t]; //恢复标记
}
}
