vlambda博客
学习文章列表

回溯算法-全排列问题(一)

回溯算法-全排列问题

一、概念

回溯算法本质上是一种暴力算法,回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的,规模较大的问题都可以使用回溯法,有“通用解题方法”的美称。

二、回溯问题本质

解决回溯问题本质上就是一个决策树的遍历过程。你只需要思考3个问题:

  1. 路径:也就是已经做出的选择

  2. 选择列表:也就是你当前可做的选择

  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 交换回溯代码

 @Test 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/

这个问题比全排列问题多出一个重复元素,这个如何思考呢?

只是每次枚举遍历剪枝是不是就可以了呢?

@Test 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(路径,选择列表) 撤销选择}