递归法
/*
当数组元素重复时,会出现重复排列
*/
public static void main(String[] args) {
int[] arr = new int[]{1,2,3,4,5,6,7,8,9};
f(arr,0);
}
static void f(int[] arr,int k){
if (k == arr.length){
System.out.println(Arrays.toString(arr));
}
for (int i = k; i < arr.length; i++) {
int t = arr[k];
arr[k] = arr[i];
arr[i] = t;
// 递归
f(arr,k+1);
// 回溯
t = arr[k];
arr[k] = arr[i];
arr[i] = t;
}
}
抓取法(掌握)
该算法不会出现重复的排列
// 需要全排列的数组
static int[] nums = {0,0,0,0,0,0,0,1,1,1,1,1};
// 访问标识
static boolean[] visit = new boolean[12];
public static void f(int k,int[] path){
if (k == path.length){
System.out.println(Arrays.toString(path));
return;
}
for (int i = 0; i < path.length; i++) {
// 现在准备选取的元素和上一个元素相同,但上一个元素还没被使用
if (i>0 && nums[i] == nums[i-1] && !visit[i-1]){
continue;
}
// 没有被用过的元素可以抓入path
if (!visit[i]){
visit[i] = true; // 标记为已访问
path[k] = nums[i];// 抓取第k个元素
f2(k+1,path); // 递归抓取第 k+1个元素
visit[i] = false;// 回溯
}
}
}
public static void main(String[] args) {
int[] res = new int[12];
f2(0,res);
}