算法与分析课程_回溯算法_拼题网_习题4_整数拆分_C++

4 整数拆分
将一个正整数拆分成若干个正整数的和。

输入格式:
一个正整数n

输出格式:
若干行，每行一个等式（每个数或者等号间都有一个空格，第一个数前没有空格，最后一个数后面没有空格，数与数之间要求非降序排列）。最后一行给出解的总个数

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

4

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

4 = 1 + 1 + 1 + 1
4 = 1 + 1 + 2
4 = 1 + 3
4 = 2 + 2
4

代码:

#include
#include
using namespace std;
void backTrack(int n,vector<vector<int>>& nums,vector<int>& ins) {int i = 1;while (n >= i) {if (!ins.empty() && i < ins.back()) {//保证升序i++;continue;}ins.emplace_back(i);n -= i;backTrack(n, nums,ins);ins.pop_back();n += i;i++;}if (ins.size() <= 1) return;if(n==0)nums.emplace_back(ins);
}
int main() {vector<vector<int>> nums;vector<int> ins;int n;cin >> n;backTrack(n,nums,ins);for (vector<int> tmp : nums) {cout << n << " = ";cout << tmp.at(0);for (int i = 1; i < tmp.size(); i++) {cout << " + " << tmp.at(i);}cout << endl;}cout << nums.size() << endl;system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！