TOP100 回溯

本文主要是介绍TOP100 回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

摘在前面（作者：liweiwei1419）：

        回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

        1.找到一个可能存在的正确的答案；
        2.在尝试了所有可能的分步方法后宣告该问题没有答案。

1.46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

输入：nums = [1]
输出：[[1]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

思路：

代码：

class Solution {public List<List<Integer>> permute(int[] nums) {int len = nums.length;// 使用一个动态数组保存所有可能的全排列List<List<Integer>> res = new ArrayList<>();if (len == 0) {return res;}boolean[] used = new boolean[len];Deque<Integer> path = new ArrayDeque<>(len);dfs(nums, len, 0, path, used, res);return res;}private void dfs(int[] nums, int len, int depth,Deque<Integer> path, boolean[] used,List<List<Integer>> res) {if (depth == len) {//全程path只有一份，因此需要在这里做一次拷贝添加进去res.add(new ArrayList<>(path));return;}for (int i = 0; i < len; i++) {if (!used[i]) {//如果没有访问过path.addLast(nums[i]);used[i] = true;//递归之前dfs(nums, len, depth + 1, path, used, res);//回退以后，清除位置used[i] = false;//去除刚刚加进来的最后一个元素path.removeLast();//递归之后}}}
}

2.78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

思路：

代码：

class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果public List<List<Integer>> subsets(int[] nums) {subsetsHelper(nums, 0);return result;}private void subsetsHelper(int[] nums, int startIndex){result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。if (startIndex >= nums.length){ //终止条件可不加return;}for (int i = startIndex; i < nums.length; i++){path.add(nums[i]);subsetsHelper(nums, i + 1);path.removeLast();}}
}

3.17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

输入：digits = ""
输出：[]

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

思路：

• 这是个排列组合问题,可以用树的形式表示出来；
• 当给定了输入字符串，比如："23"，那么整棵树就构建完成了，如下：

    

代码：

class Solution {List<String> result = new ArrayList<>();StringBuilder temp = new StringBuilder();Map<Character, List<Character>> map = new HashMap<Character, List<Character>>() {{put('2', Arrays.asList('a', 'b', 'c'));put('3', Arrays.asList('d', 'e', 'f'));put('4', Arrays.asList('g', 'h', 'i'));put('5', Arrays.asList('j', 'k', 'l'));put('6', Arrays.asList('m', 'n', 'o'));put('7', Arrays.asList('p', 'q', 'r', 's'));put('8', Arrays.asList('t', 'u', 'v'));put('9', Arrays.asList('w', 'x', 'y', 'z'));}};public List<String> letterCombinations(String digits) {if (digits == null || digits.length() == 0) {return result;}backTracking(digits, 0);return result;}private void backTracking(String digits, int num) {if (digits.length() == num) {result.add(temp.toString());return;}List<Character> list = map.get(digits.charAt(num));if (list == null) {return;}for (int i = 0; i < list.size(); i++) {Character cur = list.get(i);temp.append(cur);backTracking(digits, num + 1);temp.deleteCharAt(num);}}}

这篇关于TOP100 回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---