概念
假定有一个集合 S。
当我们要求解的结果是集合 S 的某一子集,那么对应的解空间是子集树,时间复杂度是 $O(2^{n})$。

当我们要求解的结果是集合 S 的元素的某一种排列的时候,其对应的解空间就是排列树,时间复杂度是 $O(n!)$。

算法描述
子集树:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void backtrace(int t) { if (t > n) { output(x); } for (int i = 0; i <= 1; i++) { x[t] = i; if (constraint(t) && Bound(t)) { backtrace(t + 1); } } }
|
排列树:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| void backtrace(int t) { if (t > n) { output(x); } for (int i = t; i <= n; i++) { swap(x[t], x[i]); if (constraint(t) && Bound(t)) { backtrace(t + 1); } swap(x[t], x[i]); } }
|
举例
排列树:JZ27 字符串的排列
题目大意:输入一个字符串,按字典序打印出该字符串中字符的所有排列。
思路:
按照排列树的算法描述来套进该问题,对于字符串中的第 t 个元素,依次和它之后的元素交换,可以得到不同的排列结果。然后做好去重即可。
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| import java.util.*; public class Solution { public ArrayList<String> Permutation(String str) { ArrayList<String> resList = new ArrayList<>(); if (str != null) { char[] arr = str.toCharArray(); backtrace(arr, 0, resList); Collections.sort(resList); } return resList; } public void backtrace(char[] arr, int t, ArrayList<String> resList) { if (t >= arr.length) { String tempStr = String.copyValueOf(arr); if (!resList.contains(tempStr)) { resList.add(tempStr); } return; } for (int i = t; i < arr.length; i++) { swap(arr, t, i); backtrace(arr, t + 1, resList); swap(arr, t, i); } } public void swap(char[] arr, int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
|