蓝桥杯PREV-3 带分数(搜索，剪枝，枚举)

100 可以表示为带分数的形式：100 = 3 + 69258 / 714。

还可以表示为：100 = 82 + 3546 / 197。

注意特征：带分数中，数字1~9分别出现且只出现一次（不包含0）。

类似这样的带分数，100 有 11 种表示法。

从标准输入读入一个正整数N (N<1000*1000)

程序输出该数字用数码1~9不重复不遗漏地组成带分数表示的全部种数。

注意：不要求输出每个表示，只统计有多少表示法！

import java.util.Scanner;public class Main {	static int nn,ans;	static int[] A = new int[10];	static boolean[] vis = new boolean[10];	public static void main(String[] args) {		Scanner scan = new Scanner(System.in);		nn = scan.nextInt();		dfs(A,1,9);		System.out.PRintln(ans);	}		public static void dfs(int[] A,int m,int n){		if(m==n+1){			found(A,n);			return;		}else{			for(int i=1;i<=n;i++){				if(!vis[i]){					A[m] = i;					vis[i] = true;					m++;					dfs(A,m,n);					m--;					vis[i] = false;				}			}		}		}		//搜索到根的时候，判断	public static void found(int[] A,int n){		for(int i=1;i<=n;i++){			int a = sum(A,0,i);			if(a>nn)return;			for(int j=i+(n-i)/2;j<=n-1;j++){				int b = sum(A,i+1,j);				int c = sum(A,j+1,n);				if(b>c&&b%c==0&&(a+b/c)==nn){					ans++;				}			}		}			}		//分割全排列得到的数组	public static int sum(int[] A,int start,int end){		int sum = 0;		for(int i = start;i<=end;i++){			sum = sum*10+A[i];		}		return sum;	}}