回溯算法-全排列问题(一)
回溯算法-全排列问题
一、概念
回溯算法本质上是一种暴力算法,回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。
二、回溯问题本质
解决回溯问题本质上就是一个决策树的遍历过程。你只需要思考3个问题:
路径:也就是已经做出的选择
选择列表:也就是你当前可做的选择
结束条件:也就是到达决策树底层,无法再做选择的条件
2.1 套路框架
result=[]
fuction backtrack(路径,选择列表){
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径,选择列表)
撤销选择
}
其核心就是for循环里面的递归,在递归调用之前“做选择”,在递归调用之后“撤销选择”
2.2 全排列问题
为了简单清晰,我们这次套路的全排列问题不包含重复的元素。我们给到[a,b,c]三个数字求所有的排列组合。
思路是这样的,先固定第一位a,然后第二位b,第三位c。然后可以把第二位变成c,第三位就是b了。然后第一位b,然后在穷举。
这个就是回溯算法,记录路径上的数字,走到叶子节点就得到了一个排列,遍历整个决策树之后就得到的所有排列。这个树可以称为回溯算法的“决策树”。
JAVA代码回溯
@Test
public void test() {
char[] arr = {'a', 'b', 'c'};
LinkedList<Character> track = new LinkedList<>();
backTrack(arr, track);
}
//用于存储遍历的全集
List<List<Character>> res = new LinkedList<>();
/***
* 穷举所有的排列
* @param arrays
* @param track
*/
private void backTrack(char[] arrays, LinkedList<Character> track) {
if (track.size() == arrays.length) {
res.add(new LinkedList<>(track));
return;
}
for (int i = 0; i < arrays.length; i++) {
// 已经在路径中了,直接剪枝
if (track.contains(arrays[i])) {
continue;
}
//加入遍历的选择
track.add(arrays[i]);
backTrack(arrays, track);
//移除选择
track.removeLast();
}
}
JAVA 交换回溯代码
public void test() {
char[] arr = {'a', 'b', 'c'};
LinkedList<Character> track = new LinkedList<>();
backTrack(arr, 0);
Gson gson = new Gson();
System.out.println(gson.toJson(results));
}
// 存储结果集
List<String> results = new LinkedList<>();
/***
* 交换位置 给出全部排列
* @param arrays
* @param index
*/
private void backTrack(char[] arrays, int index) {
if (index == arrays.length - 1) {
results.add(new String(arrays));
return;
}
for (int i = index; i < arrays.length; i++) {
// 固定位置index,交换
swap(arrays, index, i);
backTrack(arrays, index + 1);
swap(arrays, i, index);
}
}
/***
* 交换位置
* @param arrays
* @param left
* @param right
*/
private void swap(char[] arrays, int left, int right) {
if (left != right) {
char leftChar = arrays[left];
arrays[left] = arrays[right];
arrays[right] = leftChar;
}
}
2.3 带重复元素全排列问题
输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。 示例: 输入:s = "abc" 输出:["abc","acb","bac","bca","cab","cba"]
https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
这个问题比全排列问题多出一个重复元素,这个如何思考呢?
只是每次枚举遍历剪枝是不是就可以了呢?
public void test() {
char[] arr = {'a', 'a', 'c'};
LinkedList<Character> track = new LinkedList<>();
backTrack(arr, 0);
}
// 存储结果集
List<String> results = new LinkedList<>();
/***
* 交换位置 给出全部排列
* @param arrays
* @param index
*/
private void backTrack(char[] arrays, int index) {
if (index == arrays.length - 1) {
results.add(new String(arrays));
return;
}
//同一层不能包含相同的元素,如果包含直接跳过
HashSet<Character> sets = new HashSet<>();
for (int i = index; i < arrays.length; i++) {
if (sets.contains(arrays[i])) {
continue;
}
sets.add(arrays[i]);
// 固定位置index,交换
swap(arrays, index, i);
backTrack(arrays, index + 1);
swap(arrays, i, index);
}
}
/***
* 交换位置
* @param arrays
* @param left
* @param right
*/
private void swap(char[] arrays, int left, int right) {
if (left != right) {
char leftChar = arrays[left];
arrays[left] = arrays[right];
arrays[right] = leftChar;
}
}
三、总结
回溯算法就是一个多叉树的遍历问题,关键就是在前序遍历和后序遍历的位置做一些操作,套路框架如下:
result=[]
fuction backtrack(路径,选择列表){
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径,选择列表)
撤销选择
}