DFS求全排列三种方法 +剪枝优化

给定一个长度为 n 的可包含重复数字的序列，请你求出其所有不重复的全排列。 输入格式 第一行包含整数 n。 第二行包含 n 个整数。 输出格式 输出所有的不同排列，每种排列占一行。 在确定每种排列的输出顺序时，第一个数较小的先输出，第一个数相同时，第二个数较小的先输出，以此类推。 数据范围 1≤n≤9, 数组中包含的元素的取值范围 [1,9] 输入样例： 3 1 1 2 输出样例： 1 1 2 1 2 1 2 1 1

1.搜索顺序：从前往后依次枚举每一个位置，每个位置上有多种选择。 2.回溯：因为要枚举所有可能的选择，在一次深搜出来后，要立即恢复成上一次的状态 3.剪枝：有重复元素，剪枝过程如下：

可以自动去重

所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。 来看一个简单的例子： 43#9865#045+ 8468#6633-------------- 44445506978 其中#号代表被虫子啃掉的数字。 根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。 现在，我们对问题做两个限制： 首先，我们只考虑加法的虫食算。这里的加法是N进制加法，算式中三个数都有N位，允许有前导的0。 其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。 如果这个算式是N进制的，我们就取英文字母表的前N个大写字母来表示这个算式中的0到N-1这N个不同的数字：但是这N个字母并不一定顺序地代表0到N-1。 输入数据保证N个字母分别至少出现一次。 BADC +CBDA =DCCC 上面的算式是一个4进制的算式。 很显然，我们只要让ABCD分别代表0123，便可以让这个式子成立了。 你的任务是，对于给定的N进制加法算式，求出N个不同的字母分别代表的数字，使得该加法算式成立。 输入数据保证有且仅有一组解。 输入格式 输入包含4行。 第一行有一个正整数N(N int a = path[eq[0][i] - 'A'], b = path[eq[1][i] - 'A'], c = path[eq[2][i] - 'A']; if(a != -1&&b != -1 && c != -1) { if(t == -1) { if((a + b) % n != c && (a + b + 1) % n != c) return false; if(!i&&a + b >= n) return false; } else { if((a + b + t)% n != c) return false; if (!i && a + b + t >= n) return false; t = (a + b + t) / n; } } else { t = -1; } } return true; } bool dfs(int u) { if(u == n) return true; for(int i = 0; i st[i] = true; path[q[u]] = i; if(check()&&dfs(u + 1)) return true; st[i] = false; path[q[u]] = -1; } } return false; } int main() { cin >> n >> eq[0] >> eq[1] >> eq[2]; for(int i = n - 1, k = 0; i >= 0; i--) { for(int j = 0; j st[c] = true; q[k++] = c; } } } memset(st, 0, sizeof st); memset(path, -1, sizeof path); dfs(0); for(int i = 0; i if(start>=3 ) if(a[0]+a[1]!=a[2]) return ;//对确定的前面三个数字进行等式判断，不符合，就不继续往下搜索 if(start>=6) if(a[3]-a[4]!=a[5]) return ;//同理进行第二个等式的判断，进行剪枝 if(start>=9) if(a[6]*a[7]!=a[8]) return ; if(start>=12) if(a[11]*a[10]==a[9]) { for(int i=0;i dfs(0); cout