8-1 回溯法实验报告 (15 分)（思路+详解）

给定k个正整数，用算术运算符+，-，，/ 将这k个正整数连接起来，是最终的得数恰为m。
如果有多组满足要求的表达式，只要输出一组，每一步算式用分号隔开。
如果无法得到m，得输出“No Solution”。
样例输入:d
5 125
7 2 2 12 3
第一行输入整数的个数k和m，
第二行输入k个整数。
这只是其中一种结果
样例输出： 73=21 21*12=252 252-2=250 250/2=125

1.排列树 + 子集树
2.我们穷举所有的可能的数字组合，这是全排列，但要注意的是在全排列中，如果给出的数据有重复的数字，那么我们求的全排列后的数据是有重复的，所以我们要进行去重处理；
3.得到全排列的结果后，我们要对每一个全排列的结果进行子集树处理，因为每一次往下递归都是’+’,’-’,’*’,’/’;，递归的终止条件就是当我们统计 sum == M时候,或者是我们的操作符个数满足要求的时候，如果仅仅是操作符满足个数是不统计操作符的结果的；

#include
using namespace std;

int N,M;
int cnt = 0; 
vector >ans1;
vector path1;

vector >ans2;
vector path2;

//求出数字的全排列组合 
void backtacking1(int N,vector& vec,vector& vis){
	if(path1.size() == N){
		ans1.push_back(path1);
		return;
	}
	
	for(int i = 0; i < N; i++){
		if(vis[i] == true) continue;
		vis[i] = true;
		
		path1.push_back(vec[i]);
		backtacking1(N,vec,vis);
		
		path1.pop_back();
		vis[i] = false;
	}
}

//子集树的排列
//横向的for循环为加减乘除，纵向的为一种全排列的结果 
void backtacking2(vector& v1,vector& v2,int sum,int index){
	
	if(sum == M || path2.size() == N - 1){  //这里递归结束的条件为满足 M时 
		if(sum == M){                      //还有的是操作符号的个数不能大于 N - 1个 
			ans2.push_back(path2);
			cnt = 1;
		}
		return ;	
	}
	
	for(int i = 0; i < 4; i++){//这里小于4是有4个操作符 
		
		char ch = v1[i];
		if(ch == '+'){
			sum = sum + v2[index];
		}else if(ch == '-'){
			sum = sum - v2[index];
		}else if(ch == '*'){
			sum = sum * v2[index];
		}else if(ch == '/'){
			sum = sum / v2[index];
		}
				
		index++;//表示纵向的一种全排列结果集的下标 
		path2.push_back(ch);//将符号存进去 
		
	    backtacking2(v1,v2,sum,index);
		
		//这里的顺序不能乱 
		path2.pop_back();
		index--;
		if(ch == '+'){
			sum = sum - v2[index];
		}else if(ch == '-'){
			sum = sum + v2[index];
		}else if(ch == '*'){
			sum = sum / v2[index];
		}else if(ch == '/'){
			sum = sum * v2[index];
		}	 			
	}
} 
 
//验证全排列 
void text01(){ 
	for(int i = 0; i < ans1.size(); i++){
		for(int j = 0; j < N; j++){
			cout << ans1[i][j] << " ";
		}
		cout << endl;
	}
}

int main(){
	vectorv1;//输入的数据
	vector >v3;//记录可行解 
	vector operators(4); 
	sets[100]; 
	set:: iterator st;
	cin >> N >> M;
	
	for(int i = 0; i < N; i++){
		int num;
		cin >> num;
		v1.push_back(num);
	}
	
	cout << endl; 
	
	vector vis(N,false); 
	backtacking1(N,v1,vis); 
	
	operators[0] = '+';
	operators[1] = '-';
	operators[2] = '*';
	operators[3] = '/';
		
	for(int i = 0; i < ans1.size(); i++){
			
		vector v2;
		int count = 0; 		
		for(int j = 0; j < N; j++){			
			v2.push_back(ans1[i][j]);
			
			if(ans1[i-1][j] == ans1[i][j] && i != 0){
				count++;	                   
			}	
		}
		
		if(count == N){ // 这是为了去重的，因为在全排列中，如果有重复的元素，那么最终输出 
			continue;  //的结果是有重复的组数据的 
		}
			
		int num = v2[0];
		
		backtacking2(operators,v2,num,1);
	
		if(cnt == 1){//这里存的是满足条件的 数字组合 
			v3.push_back(v2);
		}	
		cnt = 0;
	}
	
	for(int i = 0; i < ans2.size(); i++){//v3.size() 和ans2.size()大小是一致的 
		
		cout << "操作数为:";
		for(int j = 0; j < N; j++){
			cout << v3[i][j] << ' ';
		}
		cout << endl;
		
		cout << "操作符为:"; 
		for(int j = 0; j < N - 1; j++){//N个数需要 N-1个操作符 
			cout << ans2[i][j] << ' ';
		}
		cout << endl;
	}

} 



//5 125
//7 3 12 2 2

//5 125
//7 2 2 12 3

下方的的数据按照操作符都可以得到正确结果