[C++知识库]逆推分式（全排列）

项目场景：

暴力法：

#include <iostream>
#include <cstdio>//printf
#include <cstdlib> //system
#include <bits/stdc++.h>
using namespace std;

int n;
bool us[10];

int checky(int u)
{
	int t=0;
	int u2[10]={};
	while(u)
	{
	    t=u%10;
	    u2[t]++;
	    if(us[t])return 0;//判断是否与x数字重复；
	    if(u2[t]>1)return 0;//判断是否与自身数字重复；
	    u/=10;
	}
	return 1;
}
void dfs(int u)
{

}
int main()
{
	cin>>n;
	int x=0,y=0;
	for(int a=0;a<10;a++)
	{
		x=a;
		us[a]=true;
		for(int b=0;b<10;b++)
		{
		    if(us[b]){continue;}
			x=x*10+b;
			us[b]=true;
			for(int c=0;c<10;c++)
			{
			    if(us[c]){continue;}
				x=x*10+c;
				us[c]=true;
				for(int d=0;d<10;d++)
				{
				    if(us[d]){continue;}
					x=x*10+d;
					us[d]=true;
					for(int e=0;e<10;e++)
					{
					    if(us[e]){continue;}
						x=x*10+e;
						us[e]=true;
						y=n*x;
						//printf("z%d，%d",y,x); 
						if(checky(y)&&(y<98765))
						{
							printf("%d/%d=%d",y,x,n); 
							cout<<endl;
						}
						x=x/10;//要还原现场
						us[e]=false;
					}
					x=x/10;//要还原现场
					us[d]=false;
				}
				x=x/10;//要还原现场
				us[c]=false;
			}	
			x=x/10;//要还原现场
			us[b]=false;
		}
		x=x/10;//要还原现场
		us[a]=false;
	}
	system("pause");
	return 0;
}
        }

原因分析：

太长了

解决方案：递归

#include <iostream>
#include <cstdio>//printf
#include <cstdlib> //system
#include <bits/stdc++.h>
using namespace std;

int n;
bool us[10];
int x=0,y=0;
int checky(int u)
{
	int t=0;
	int u2[10]={};
	while(u)
	{
	    t=u%10;
	    u2[t]++;
	    if(us[t])return 0;//判断是否与x数字重复；
	    if(u2[t]>1)return 0;//判断是否与自身数字重复；
	    u/=10;
	}
	return 1;
}
void dfs(int u)
{

    if(u==5)
    {
        y=n*x;
		if(checky(y)&&(y<98765)&&(y>1234))
		{
			printf("%d/%d=%d",y,x,n); 
			cout<<endl;
		}
		return;//要及时退出！！！！
    }
    for(int i=0;i<10;i++)
    {
        if(us[i]){continue;}
        x=x*10+i;
        us[i]=true;
        dfs(u+1);
        x=x/10;//要还原现场
		us[i]=false;//要还原现场
    }
}
int main()
{
	cin>>n;
	int x=0,y=0;
	dfs(0);
	system("pause");
	return 0;
}

提示：
例如：