数的划分

题目描述

将整数 n n n 分成 k k k 份，且每份不能为空，任意两份不能相同(不考虑顺序)。

例如： n = 7 n=7 n=7， k = 3 k=3 k=3 ，下面三种分法被认为是相同的。

{1，1，5}；{1，5，1}；{5，1，1}{1，1，5}；{1，5，1}；{5，1，1}；

问有多少种不同的分法。 输出一个整数，即不同的分法。

输入格式

两个整数 n n n ， k   ( 6 < n ≤ 200 ,   2 ≤ k ≤ 6 ) k \ (6 < n \leq 200, \ 2 \leq k \leq 6) k (6<n≤200, 2≤k≤6)，中间用单个空格隔开。

输出格式

一个整数，即不同的分法。

输入样例

7 3

输出样例

4

样例解释

四种分法为：

{1，1，5}；{1，2，4}；{1，3，3}；{2，2，3}{1，1，5}；{1，2，4}；{1，3，3}；{2，2，3}。

解题思路

两种方法：一种是纯粹的递归，第二种是搜索+剪枝，具体剪枝的细节看代码注释。

标准程序

解法1：

#include <cstdio>
#include <iostream>
using namespace std;

int dfs(int n, int k) {
    if (n == 0 || k == 0 || n < k) return 0;
    if (n == k || k == 1) return 1;
    //分两种情况讨论，即从n中划分一个出来 dfs(n - 1, k - 1)，
    //另一种则不划分,其数量应该是 dfs(n - k, k)
    return dfs(n - k, k) + dfs(n - 1, k - 1);
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << dfs(n, k) << endl;
    return 0;
}

解法2：

#include <cstdio>
#include <iostream>
using namespace std;
int a[10], n, k, ans;

void dfs(int s, int u) {
    if (s == n) return;
    if (u == k) {
        if (n - s >= a[u - 1])  ans++;  //剩下的数如果大于前一位则可行，计数器+1
        return;
    }
    //此处做了剪枝，为避免重复，后一个位置的值一定要大于等于前一个位置的值
    //同时剩下元素/剩下个数应该是该位置能够排列的最大元素
    for (int i = a[u - 1]; i <= n / (k - u + 1); i++) {
        a[u] = i;
        s += i;
        dfs(s, u + 1);
        s -= i;
        a[u] = 0;
    }
}

int main() {
    cin >> n >> k;
    a[0] = 1;
    dfs(0, 1);
    cout << ans << endl;
    return 0;
}