当前位置：首页 > article >正文

【算法题解】——自然数拆分问题

article 2025/1/5 5:46:57

【算法题解】——自然数拆分问题

题目描述

一个整数N(N > 1)可以拆分成若干个大于等于1的自然数之和，请你输出所有不重复的拆分方式。
所谓拆分方式的重复性判定如下：
例如 6 = 3 + 2 和 6 = 2 + 3，就是重复的拆分方式。

输入格式:
一个正整数N（1≤N≤52）。

注意：本题N的上限52，是经过PTA平台服务器测试后得到的上限，能够保证较好的搜索策略在PTA提交，在1s内求解。本地PC机上，即使较好方法运行时间也可能大于1s，如果觉得方法没问题，可以先提交试试。

输出格式:
按照拆分方案的字典序由小大到大，输出所有方案，请参考输出样例

输入样例:
在这里给出一组输入。例如：

输出样例:
在这里给出相应的输出。例如：

6=1+1+1+1+1+1
6=1+1+1+1+2
6=1+1+1+3
6=1+1+2+2
6=1+1+4
6=1+2+3
6=1+5
6=2+2+2
6=2+4
6=3+3
6=6

代码

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void findPartitions(int n, int start, vector<int>& current, vector<vector<int>>& results) {
    // 如果剩余值为 0，保存当前方案
    if (n == 0) {
        results.push_back(current);
        return;
    }

    // 从起始值开始尝试分割
    for (int i = start; i <= n; ++i) {
        current.push_back(i); // 添加当前数字到拆分方案
        findPartitions(n - i, i, current, results); // 递归求解剩余部分
        current.pop_back(); // 回溯
    }
}

int main() {
    int N;
    cin >> N;

    vector<int> current;          // 当前拆分方案
    vector<vector<int>> results;  // 所有拆分方案

    // 找到所有不重复的拆分
    findPartitions(N, 1, current, results);

    // 按格式输出结果
    for (const auto& partition : results) {
        cout << N << "=";
        for (size_t i = 0; i < partition.size(); ++i) {
            cout << partition[i];
            if (i != partition.size() - 1) cout << "+";
        }
        cout << endl;
    }

    return 0;
}

分析解答

这是一个经典的组合问题，目标是找出一个正整数所有可能的加法划分方式。

让我们先通过一个具体的例子来理解这个算法：

假设输入 N = 4，我们来看看算法是如何工作的：

函数结构解析

void findPartitions(int n,                    // 待划分的数
                   int start,                 // 当前可以使用的最小数
                   vector<int>& current,      // 当前正在构建的划分方案
                   vector<vector<int>>& results) // 存储所有划分方案

递归的工作原理
以N=4为例，让我们跟踪完整的递归过程：

第一层递归（n=4, start=1）：

- 选择1：current=[1]
  - 第二层递归（n=3, start=1）
    - 选择1：current=[1,1]
      - 第三层...current=[1,1,1]
        - 第四层...current=[1,1,1,1] ✓ (找到方案4=1+1+1+1)
    - 选择2：current=[1,2] 
      - 第三层...current=[1,2,1] ✓ (找到方案4=1+2+1)
    - 选择3：current=[1,3] ✓ (找到方案4=1+3)
- 选择2：current=[2]
  - 第二层递归（n=2, start=2）
    - 选择2：current=[2,2] ✓ (找到方案4=2+2)
- 选择3：current=[3]
  - 继续递归...
- 选择4：current=[4] ✓ (找到方案4=4)

关键代码部分解析

// 基本情况：当待划分的数变为0时
if (n == 0) {
    results.push_back(current);  // 找到一个有效的划分方案
    return;
}

// 尝试所有可能的数字
for (int i = start; i <= n; ++i) {
    current.push_back(i);    // 选择当前数字
    findPartitions(n - i, i, current, results);  // 递归处理剩余的数
    current.pop_back();      // 回溯：撤销选择，尝试下一个可能的数字
}

算法的精妙之处

避免重复：使用start参数确保每个新的数字不小于之前使用的数字，这样可以避免生成重复的划分方案（比如避免同时出现1+2和2+1）
回溯设计：使用vector的push_back和pop_back操作实现回溯，保证在尝试不同方案时不会互相影响
递归终止：当n变为0时找到一个完整的划分方案，这是一个清晰的递归终止条件

输出格式处理

for (const auto& partition : results) {
    cout << N << "=";
    for (size_t i = 0; i < partition.size(); ++i) {
        cout << partition[i];
        if (i != partition.size() - 1) cout << "+";
    }
    cout << endl;
}