关于全排列的问题代码如下:
public class QuanPaiLie {
static void backtrack(LinkedList<LinkedList<Integer>> res, int[] nums, LinkedList<Integer> track) {
// 如果深度等于该nums则将path添加至res
if (track.size() == nums.length) {
res.add(new LinkedList(track));
return;
}
// 对树进行搜索
for (int i = 0; i < nums.length; i++) {
// 如果track中包含nums[i],跳过,该判断为搜索的条件
if (track.contains(nums[i]))
continue;
//否则,track中加入nums[i]
track.add(nums[i]);
//继续搜索
backtrack(res, nums, track);
// 弹出元素,回溯的关键,就是剪枝
track.removeLast();
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
LinkedList<LinkedList<Integer>> res = new LinkedList<>();
LinkedList<Integer> list = new LinkedList<>();
backtrack(res, nums, list);
res.forEach(integers -> {
System.out.println(integers);
});
}
}
需要注意的是,在res.add我们的track时候需要new一个LinkedList,可能是深拷贝的问题,不new的话添加的就是空值
回溯算法的框架如下:
List <Value> result;
void backtrack(路径,选择列表){
if(满足结束条件){
result.add(路径);
return;
}
for(选择:选择列表){
做选择;
backtrack(路径,选择列表);
撤销选择;
}
}