解析

题目内容:

题意:

输出不重复的,将一个正整数n分成k份正整数的所有组合的数量(元素相同即为重复).

输入描述:

仅一行,n与k之间用空格隔开.

输出描述:

输出组合的总数.

分析:

限制条件:不能重复.

(以DFS为基本思路)

  1. 如何保证结果不会重复?
    将系统给出和自身给出的测试样例来进行枚举,能注意到所有互相重复的项,必包含有且仅有一个非逆序的项.
    所以,我们可以剔除逆序的项,来保证结果的唯一性.
    最终我们采用顺序且递进的方式来进行查找,这也是该题DFS的核心.
    但要注意的是,即便保证了前面的项能够满足上述的条件,但后面的项对于当前的项来说,也要遵循该规则.
    因此,我们需要规定一个上限,一个确保不能重复的上限.
    不妨举个现实生活中的例子:
    一块圆柱形的蛋糕已经被分走了一部分,需要在剩下的蛋糕里面进行分配,且不能重复.
    不难得出,想要遵循这个规定,所"切"的位置不能超过每块蛋糕平均分配的值.
    因此,上限可以由如下的公式进行表示:

    上限 = (总元素 - 已分配元素) / (总块数 - 已分配的块数).
    (题外话:由于C/C++中除法向下取整的特性,能够恰好满足非逆序的需求)

  2. 如何驱动DFS?
    DFS是一个递归的过程,在进行递归搜索的过程中必须要用到上一层的数据.
    仅对该题而言,在第一点的分析中,得出两个结论:

    1. 需要遵循非逆序的原则来解出合适的答案,因此,前一项必定不大于后一项,故需要传递上一层元素的值.
    2. 需要确定每一层元素遍历的上限,因此也需要传递已分配元素的总和.

    将以上两点理解并写入dfs中元素的遍历,就可以正确进行搜索.

注:由于最后一个元素是被总元素n和已分配元素之和共同确定,所以不做考虑.只需要在上一层判断已分配元素之和小于总元素之和即可.

代码

#include <bits/stdc++.h>

using namespace std;

int result = 0;
int n, k;

void dfs(int layer, int para, int pre)
{
    if (layer == k - 1)
    {
        result++;
        return;
    }
    for (int i = pre; i <= (n - para) / (k - layer); i++)
    {
        if ((i + para < n) && i)
        {
            // cout << i << endl;
            dfs(++layer, para + i, i);
            layer--;
        }
    }
    return;
}

int main()
{

    cin >> n >> k;

    dfs(0, 0, 0);

    cout << result << endl;
    return 0;
}