[depth first search] Ji suanke: a joke of replacement

The question ：

Given a string , Find the separation scheme , Separate the string into non repeating numbers

Ideas ：

Because the string length is less than 100, therefore n yes 2 digit .

You can separate them in groups , You can also work in groups of two

（ It can be seen as walking through a one-dimensional maze , from S[0] Go to the S[n-1], One step at a time , Or take two steps .）

DFS(int index)// The subscript

prune ：

（1） Feasibility pruning （ Transboundary ）：if(index>=n)return;

（2） Repetitive pruning （vis Array ）： If there have been numbers , There is no need to search

（3） Optimal pruning （ With global variables flag）： If there is already a set of solutions , Then there is no need to search

To make a choice ：

Mark the number

Digital join vector Array

DFS(index+1)// Take a step

Recall mark

vector.pop_back();

Mark the number

Digital join vector Array

DFS(index+2)// Take two steps

Recall mark

vector.pop_back();

 

#include<iostream>
#include<string>
#include<vector>
using namespace std;
bool vis[100];
vector<int>num;
string s;
int n;
bool flag=false;
void dfs(int step){
	if(flag){
		return;
	}
	if(step>=s.size()){
	    for(int i=0;i<num.size();i++){
	    	cout<<num[i]<<" ";
		}
		flag=true; 
		return;	
	}	
	if(!vis[s[step]-'0']){
	vis[s[step]-'0']=true;
	num.push_back(s[step]-'0');
	dfs(step+1);
	vis[s[step]-'0']=false;
	num.pop_back();
    }
	if((s[step]-'0')!=0&&!vis[(s[step]-'0')*10+s[step+1]-'0'])
	{
	vis[(s[step]-'0')*10+s[step+1]-'0']=true;
	num.push_back((s[step]-'0')*10+s[step+1]-'0');
	dfs(step+2);
	vis[(s[step]-'0')*10+s[step+1]-'0']=false;
	num.push_back((s[step]-'0')*10+s[step+1]-'0');
	}
	
}
int main(){
	cin>>s;
	dfs(0);
}