题解|整数拆分为若干项和

题目：输入n，将数字分解显示，如6可以显示为6，5+1，4+2，4+1+1.....（不重复显示）

解答：

#include <bits/stdc++.h>
using namespace std;
int N=22;
set<vector<int>>st;
void func(int n,vector<int>v){
	//递归出口 
	if(n==0){
		//从大到小排序以保证在set中唯一 
		sort(v.rbegin(),v.rend());
		int sum=0;
		for(auto a:v)sum+=a;
		//如果满足条件（和为N）且没有被输出过，则输出 
		if(sum == N&&st.find(v)==st.end()){
			st.insert(v);
			for(auto a:v)
				cout<<a<<" ";
			cout<<endl;
		}
	}else{
		//开始递归 
		for(int i =1;i<=n;i++){
			vector<int>newV;
			//复制一下元素，不能直接传v 
			for(auto a:v)newV.push_back(a);
			newV.push_back(i); 
			func(n-i,newV);
		}	
	}
}
int main() {
	//数字分解
	vector<int>v; 
	func(N,v);
}

时间复杂度很大，但是也想不出什么好方法了。。。

N=22跑了12秒，大约N每+1就翻一倍