回溯法

自然数拆分问题

又刷了刷PTA上的题目,重写了一遍题感觉比之前代码简洁不少。

题目

一个整数N(N > 1)可以拆分成若干个大于等于1的自然数之和,请你输出所有不重复的拆分方式。

所谓拆分方式的重复性判定如下:给定N=a​1​​+a​2​​+…am1​​ 和 N=b​1​​+b​2​​+…bm2​​ 表示整数N的两种拆分方式。对于∀ai​​,bj​​≥1,令集合A={ai​​∣1≤im​1​​},B={bj​​∣1≤jm​2​​}。若满足集合A=B,则称这两种拆分方式是重复的。

例如 6 = 3 + 2 和 6 = 2 + 3, 就是重复的拆分方式。

输入格式:

一个正整数N(1≤N≤52)。

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

输出格式:

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

输入样例:

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

6

输出样例:

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

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

题解

典型的回溯法,穷举所有可能性。注意的是这里要去除重复,观察一下如果已经对1的情况穷举完,下一次就从2开始并且不能包括1。这个特点和之前做过的很多题都类似。

#include <algorithm>
#include <iostream>
using namespace std;
void backtrace(int index, string &str, int now);

int num;
int main() {
  cin >> num;
  string str;
  backtrace(num, str, 1);
  system("pause");
}

void backtrace(int index, string &str, int now) {
  if (index == 0) {
    // cout <<num<<"=" + str << endl;  //慢的不行cout
    printf("%d=%s",num,str.c_str());   //c里面没有string,需要转化一下
    putchar(10);
  }
  for (int i = now; i <= index; i++) {
    string temp = str;
    if (!str.empty()) {
      str += '+';
    }
    str += to_string(i);
    backtrace(index - i, str, i);
    str = temp;
  }
}

实测cout比printf慢的不是一点半点。不过我还是喜欢c++。

image 28