回溯算法之全排列 力扣刷题

关于全排列的问题代码如下:

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(路径,选择列表);
    撤销选择;
}
}
上一篇:opencv第6讲--tracking_bar的使用


下一篇:Java中==和equals()的区别