前言
之前小六六一直觉得自己的算法比较菜，算是一个短板吧，以前刷题也还真是三天打鱼，两台晒网，刷几天，然后就慢慢的不坚持了，所以这次，借助平台的活动，打算慢慢的开始开刷，并且自己还会给刷的题总结下，谈谈自己的一些思考，和自己的思路等等，希望对小伙伴能有所帮助吧，也可以借此机会把自己短板补一补，希望自己能坚持下去呀
- 六六力扣刷题回溯之combinations（组合
- 六六力扣刷题回溯之组合总和
- 六六力扣刷题回溯之电话号码的字母组合
- 六六力扣刷题回溯之分割回文串
- 六六力扣刷题回溯之复原 IP 地址
- 六六力扣刷题回溯之子集
- 六六力扣刷题回溯之子集2
题目
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入： nums = [1,2,3] 输出： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
输入： nums = [0,1] 输出： [[0,1],[1,0]]
题解
package com.six.finger.leetcode.five; /* 输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] */ import java.util.ArrayList; import java.util.List; public class twentyone { public static void main(String[] args) { int[] nums={1,2,3}; List<List<Integer>> permute = permute(nums); System.out.println(permute); } public static List<List<Integer>> permute(int[] nums) { //先判断临界条件 if (nums.length == 0) { return new ArrayList<>(); } //设置一个返回值 List<List<Integer>> res = new ArrayList<>(); //设置我们存储路径的path List<Integer> path = new ArrayList<>(); //存放使用的过程 boolean[] used = new boolean[nums.length]; //回溯函数 backtracking(res, path, used, nums); return res; } private static void backtracking(List<List<Integer>> res, List<Integer> path, boolean[] used, int[] nums) { //判断退出条件 if (path.size() == nums.length) { res.add(new ArrayList<>(path)); return; } //回溯函数 for (int i = 0; i < nums.length; i++) { //先判断 if (used[i]) { continue; } path.add(nums[i]); used[i] = true; backtracking(res, path, used, nums); path.remove(path.size() - 1); used[i] = false; } } }
解题模版
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
- 第一步 先判断临界条件
- 第二步 设置一个返回值
- 第三步 存放我们使用过的路径，可以用boolean[] 也可以用一个map
- 第四步，写回溯函数backtracking
- 第五步，回溯的终止条件
- 第六步，循环树的宽度
- 第七步，判断当前剩余的节点使用情况，然后把它加入到path中
- 第八步，继续遍历树的深度，
- 第九步，遍历到最低处，然后往回做减法，之前做了啥，现在往反向做
结束
今天就这么多了，回溯就写这么多了，下次换个算法写了，好了 我是小六六，三天打鱼，两天晒网！
