我们可以借助递归来解决问题。递归很难解释,所以我创建了一个递归树来演示它。
这是相同的代码。
package org.arpit.java2blog;
import java.util.ArrayList;
import java.util.List;
public class PermutateArray {
public static void main(String[] args) {
PermutateArray pa=new PermutateArray();
int[] arr= {10, 20, 30};
List<List<Integer>> permute = pa.permute(arr);
System.out.println("Permuations of array : [10, 20, 30] are:");
System.out.println("=========================================");
for(List<Integer> perm:permute)
{
System.out.println(perm);
}
}
public List<List<Integer>> permute(int[] arr) {
List<List<Integer>> list = new ArrayList<>();
permuteHelper(list, new ArrayList<>(), arr);
return list;
}
private void permuteHelper(List<List<Integer>> list, List<Integer> resultList, int [] arr){
// Base case
if(resultList.size() == arr.length){
list.add(new ArrayList<>(resultList));
}
else{
for(int i = 0; i < arr.length; i++){
if(resultList.contains(arr[i]))
{
// If element already exists in the list then skip
continue;
}
// Choose element
resultList.add(arr[i]);
// Explore
permuteHelper(list, resultList, arr);
// Unchoose element
resultList.remove(resultList.size() - 1);
}
}
}
}
当你运行上面的程序时,你会得到以下输出:
Permuations of array : [10, 20, 30] are:
=========================================
[10, 20, 30] [10, 30, 20] [20, 10, 30] [20, 30, 10] [30, 10, 20] [30, 20, 10]
我已经用下图说明了递归是如何在这里工作的。
您需要在新窗口中打开此图表并对其进行缩放。
由于数组中有 3 个元素,因此每个节点有 3 个分支。