回溯经典题目：黑板上排列组合你舍得解开吗？

2024-03-15 01:27| 来源: 网络整理| 查看: 265

回忆往前挪十年，那一年的数学正好学到排列组合，那一天最火的电影是《那些年一起追过的女孩》。课间广播台播放的是《那些年一起追过的女孩》主题曲，其中有一句：黑板上排列组合你舍得解开吗？巧的是黑板上的题目确实也是排列组合。其中一个同学说：哎，现在黑板上不正好是排列组合吗？但是没人理他，不过这个场景我永远的记住了。

扯远了。

在leetcode上有一堆排列、组合、子集的问题，所有这些排列组合的题目的解法都是同一个算法框架——回溯。看完这篇文章，下面这些排列组合的题目就全部可以AC了。

全排列：https://leetcode-cn.com/problems/permutations/全排列2：https://leetcode-cn.com/problems/permutations-ii/字符串的排列：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/组合：https://leetcode-cn.com/problems/combinations/组合总和：https://leetcode-cn.com/problems/combination-sum/组合总和2：https://leetcode-cn.com/problems/combination-sum-ii/组合总和3：https://leetcode-cn.com/problems/combination-sum-iii/组合总和4：https://leetcode-cn.com/problems/combination-sum-iv/子集：https://leetcode-cn.com/problems/subsets/子集2：https://leetcode-cn.com/problems/subsets-ii/ 0.回溯框架前情提要

回溯说起来可能比较高大上。但是如果说深度优先遍历，你肯定会说，这个我知道这个我知道，我我我我（见卡姆表情包）。

对，回溯只是一种变了形的深度优先遍历，深度优先遍历在遍历的时候直接无差别对各种情况开枝散叶，直到所有情况都遍历完成。而回溯是更有章法一点的深度优先遍历，他使用同一个列表存储选择路径，当完成选择之后还会把这个选取去掉换成另一个选择，使用这样方式放所有可能性遍历完成。

总结一下，他们的区别主要就两个。

深度优先遍历是直接对各种情况开枝散叶遍历，回溯是通过选择和回退选择遍历所有情况。深度优先遍历使用的是不同列表，回溯使用的是同一个列表。

下面有9道题目，咱们先用第一道题全排列讲一下普通深度优先遍历和回溯的区别，并引出回溯框架。后面就调几道套用回溯框架来展示结果了。

1.全排列题意

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

permutations 美[ˌpɜːrmjʊ'teɪʃn] 英[pɜːmjʊ'teɪʃ(ə)n] n. 变化组合 / 排列 / 置换 / 挑选

翻译：给定一个不同数字的列表，返回所有可能的排列。你可以以任何顺序返回。

示例:

输入: [1,2,3]

输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路推演

这种题目我们在上中学的时候就会在演算本上画出来，第一位选了1之后，我们第二位可以选择2或者3，第二位选择了2之后，第三位只能选择3，第二位选择了3之后，第三位只能选择2。

根据上面的思路我们可以写出深度优先遍历的代码，一次选择一个数字通过递归往深处选择，直到选择的数量等于三为止，还需要考虑不能有重复的数字。

我们看一下代码是这样写的：

class Solution { public List permute(int[] nums) { //1.使用空列表开始深度优先遍历 dfs(nums, new ArrayList()); return res; } List res = new ArrayList(); private void dfs(int[] nums, List list) { //2.终止条件：如果列表选择的数字超过了数组数量，则终止选择。 if(list.size() >= nums.length) { res.add(list); return; } //3.遍历所有可能的选择 for(int i = 0; i = nums.length) { res.add(new ArrayList(list)); return; } //3.遍历所有可能的选择 for(int i = 0; i = k || sum > n) { return; } //需要遍历的所有可能：1-9。 //过滤条件：因为每个数字最多遍历一次，所以新一次的遍历要在之前的下标之后开始遍历。 for(int i = start; i

【本文地址】

公司简介

联系我们