回溯法： 分为迭代回归和递归回归，一个集合｛1,2,3,4,5｝，那么它的全排列，是{1,2,3,4,5},{1,2,3,5,4}....., 共有 5!＝120种。对回溯法控制流程的抽象描述。每个解都在X(1:n)中生成一个解,一经确定就立即输出。在X(l),…,X(k-l)已被选定的情况下，T(X(l), …,* X(k-1))给出X(k)的所有可能的取值。限界函数B(X(l),…,X(k)) 判断哪些元素X(k)满足隐式约束条件。伪代码如下：
* int k，n ；int X[n]； * k=1； * while(k>＝0) { * while(a[k]<=n){ * if((X[1],…,X[k])是一条已抵达一答案结点的路径) { * print(X[1],…,X[k]) }else{ * ++k； } //考虑下一个集合 * else { a[k]=0; --k； } //回溯到先前的集合 } } 迭代回溯java代码如下： public static void main(String[] args) { int k = 0; int n = 5; int[] a = new int[5]; int count = 0; while (k >= 0) { while(k < n && a[k] < n ){ a[k] = a[k]+1; if(legal(a,k,a[k])){ if(k == 4){ for(int e : a){ System.out.print(e); } System.out.println(); count++; System.out.println("count" + count); break; }else{ k++; } } } //回溯 a[k]=0; --k; } } //判断是否有重复的元素 public static boolean legal(int[] a, int k, int n) { for (int i = 0; i < k; i++) { if (a[i] == n) { return false; } } return true; }
输入的结构如下：
count: 1:1 2 3 4 5 count: 2:1 2 3 5 4 count: 3:1 2 4 3 5 count: 4:1 2 4 5 3 count: 5:1 2 5 3 4 count: 6:1 2 5 4 3 count: 7:1 3 2 4 5 count: 8:1 3 2 5 4 count: 9:1 3 4 2 5 count: 10:1 3 4 5 2
count: 11:1 3 5 2 4 count: 12:1 3 5 4 2 count: 13:1 4 2 3 5 count: 14:1 4 2 5 3 count: 15:1 4 3 2 5 count: 16:1 4 3 5 2 count: 17:1 4 5 2 3 count: 18:1 4 5 3 2 count: 19:1 5 2 3 4 count: 20:1 5 2 4 3
count: 21:1 5 3 2 4 count: 22:1 5 3 4 2 count: 23:1 5 4 2 3 count: 24:1 5 4 3 2 count: 25:2 1 3 4 5 count: 26:2 1 3 5 4 count: 27:2 1 4 3 5 count: 28:2 1 4 5 3 count: 29:2 1 5 3 4 count: 30:2 1 5 4 3
count: 31:2 3 1 4 5 count: 32:2 3 1 5 4 count: 33:2 3 4 1 5 count: 34:2 3 4 5 1 count: 35:2 3 5 1 4 count: 36:2 3 5 4 1 count: 37:2 4 1 3 5 count: 38:2 4 1 5 3 count: 39:2 4 3 1 5 count: 40:2 4 3 5 1
count: 41:2 4 5 1 3 count: 42:2 4 5 3 1 count: 43:2 5 1 3 4 count: 44:2 5 1 4 3 count: 45:2 5 3 1 4 count: 46:2 5 3 4 1 count: 47:2 5 4 1 3 count: 48:2 5 4 3 1 count: 49:3 1 2 4 5 count: 50:3 1 2 5 4
count: 51:3 1 4 2 5 count: 52:3 1 4 5 2 count: 53:3 1 5 2 4 count: 54:3 1 5 4 2 count: 55:3 2 1 4 5 count: 56:3 2 1 5 4 count: 57:3 2 4 1 5 count: 58:3 2 4 5 1 count: 59:3 2 5 1 4 count: 60:3 2 5 4 1
count: 61:3 4 1 2 5 count: 62:3 4 1 5 2 count: 63:3 4 2 1 5 count: 64:3 4 2 5 1 count: 65:3 4 5 1 2 count: 66:3 4 5 2 1 count: 67:3 5 1 2 4 count: 68:3 5 1 4 2 count: 69:3 5 2 1 4 count: 70:3 5 2 4 1
count: 71:3 5 4 1 2 count: 72:3 5 4 2 1 count: 73:4 1 2 3 5 count: 74:4 1 2 5 3 count: 75:4 1 3 2 5 count: 76:4 1 3 5 2 count: 77:4 1 5 2 3 count: 78:4 1 5 3 2 count: 79:4 2 1 3 5 count: 80:4 2 1 5 3
count: 81:4 2 3 1 5 count: 82:4 2 3 5 1 count: 83:4 2 5 1 3 count: 84:4 2 5 3 1 count: 85:4 3 1 2 5 count: 86:4 3 1 5 2 count: 87:4 3 2 1 5 count: 88:4 3 2 5 1 count: 89:4 3 5 1 2 count: 90:4 3 5 2 1
count: 91:4 5 1 2 3 count: 92:4 5 1 3 2 count: 93:4 5 2 1 3 count: 94:4 5 2 3 1 count: 95:4 5 3 1 2 count: 96:4 5 3 2 1 count: 97:5 1 2 3 4 count: 98:5 1 2 4 3 count: 99:5 1 3 2 4 count:100:5 1 3 4 2
count:101:5 1 4 2 3 count:102:5 1 4 3 2 count:103:5 2 1 3 4 count:104:5 2 1 4 3 count:105:5 2 3 1 4 count:106:5 2 3 4 1 count:107:5 2 4 1 3 count:108:5 2 4 3 1 count:109:5 3 1 2 4 count:110:5 3 1 4 2
count:111:5 3 2 1 4 count:112:5 3 2 4 1 count:113:5 3 4 1 2 count:114:5 3 4 2 1 count:115:5 4 1 2 3 count:116:5 4 1 3 2 count:117:5 4 2 1 3 count:118:5 4 2 3 1 count:119:5 4 3 1 2 count:120:5 4 3 2 1
2.一个数组int[] a的取3个元素的全排列，假如int[] a = {-1,2,1,3};
public static List<List<Integer>> threeSum3(int[] nums) { int size = nums.length; int i = 0; //存储排列的结果 int[] result = new int[4]; //store index int[] index = new int[4]; index[0] = -1; int j = 1; while (i >= 0 && j > 0) { while (i < size && j < result.length && j > 0) { result[j] = nums[i]; index[j] = i; if (legal(index,j,i)) { if (j == index.length-1) { List<Integer> temp = new ArrayList<>(); for (int k = 1; k < result.length; k++) { temp.add(result[k]); } retList.add(temp); temp = null; }else { j++; i=-1; } } i++; } j--; //回溯 i = index[j]+1; } return retList; } /** * * @param index * @param j * @param k * @return */ public static boolean legal(int[] index, int j,int k) { for (int i = 1;i < j; i++) { if (index[i] == k) { return false; } } return true; }
public static void main(String[] args) {
int nums[] = {-1, 2, 1};
List<List<Integer>> list = threeSum3(nums);
System.out.println(list);
System.out.println(list.size());
}
输入结果：
[[-1, 2, 1], [-1, 1, 2], [2, -1, 1], [2, 1, -1], [1, -1, 2], [1, 2, -1]]
6