LeetCode 热题 100：https://leetcode.cn/studyplan/top-100-liked/

---

---

八、二叉树

二叉树的定义：

public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) {this.val = val;}TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}

---

94. 二叉树的中序遍历（递归与非递归）

递归方式：

class Solution {List<Integer> res = new ArrayList<>();/*** 输入：root = [1,null,2,3] * 输出：[1,3,2]*/public List<Integer> inorderTraversal(TreeNode root) {InOrder(root);return res;}public void InOrder(TreeNode root){if(root != null){InOrder(root.left);res.add(root.val);InOrder(root.right);}}
}

非递归方式：

class Solution {public List<Integer> inorderTraversal(TreeNode root) {Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈List<Integer> list = new ArrayList<>();TreeNode p = root;while(p != null || !stack.isEmpty()){if(p != null){stack.push(p);p = p.left;}else{p = stack.pop();list.add(p.val);p = p.right;}}return list;}
}

---

补充：144. 二叉树的前序遍历（递归与非递归）

题目链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/description/

递归做法：

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> preorderTraversal(TreeNode root) {preOrder(root);return list;}public void preOrder(TreeNode root){if(root != null){list.add(root.val);preOrder(root.left);preOrder(root.right);}}
}

非递归做法：

class Solution {public List<Integer> preorderTraversal(TreeNode root) {Deque<TreeNode> stack = new LinkedList<>(); // 双端队列模拟栈List<Integer> list = new ArrayList<>();TreeNode p = root;while(p != null || !stack.isEmpty()){if(p != null){list.add(p.val);stack.push(p);p = p.left;}else{p = stack.pop();p = p.right;}}return list;}
}

---

补充：145. 二叉树的后序遍历（递归与非递归）

题目链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

递归做法：

class Solution {List<Integer> list = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {postOrder(root);return list;}public void postOrder(TreeNode root){if(root != null){postOrder(root.left);postOrder(root.right);list.add(root.val);}}
}

非递归做法：

class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();Deque<TreeNode> stack = new LinkedList<>();TreeNode p, r;p = root;r = null;while(p != null || !stack.isEmpty()){if(p != null){ // 走到最左边stack.push(p);p = p.left;}else{ // 向右p = stack.peek(); // 得到栈顶元素if(p.right != null && p.right != r){ // 右子树存在，且未访问p = p.right;}else{ // 否则弹出节点并访问p = stack.pop();list.add(p.val);r = p; // 记录最近访问节点p = null; // 节点访问后，重置 p}}}return list;}
}

---

104. 二叉树的最大深度

class Solution {/*** 输入：root = [3,9,20,null,null,15,7]* 输出：3*/public int maxDepth(TreeNode root) {return getMaxDepth(root);}private int getMaxDepth(TreeNode root) {if (root == null) {return 0;}int left = getMaxDepth(root.left);int right = getMaxDepth(root.right);return Math.max(left, right) + 1;}
}

---

226. 翻转二叉树

class Solution {public TreeNode invertTree(TreeNode root) {reverseTree(root);return root;}private void reverseTree(TreeNode root) {if (root == null) {return;}TreeNode temp = root.left;root.left = root.right;root.right = temp;reverseTree(root.left);reverseTree(root.right);}
}

---

101. 对称二叉树

class Solution {/*** 输入：root = [1,2,2,3,4,4,3]* 输出：true*/public boolean isSymmetric(TreeNode root) {if (root == null) {return true;}return recur(root.left, root.right);}public boolean recur(TreeNode l, TreeNode r) {if (l == null && r == null) {return true;}if (l == null || r == null || l.val != r.val) {return false;}return recur(l.left, r.right) && recur(l.right, r.left);}
}

---

543. 二叉树的直径

class Solution {int diam;/*** 输入：root = [1,2,3,4,5]* 输出：3* 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。*/public int diameterOfBinaryTree(TreeNode root) {getMaxDepth(root);return diam;}public int getMaxDepth(TreeNode root) {if (root == null) {return 0;}int left = getMaxDepth(root.left);int right = getMaxDepth(root.right);diam = Math.max(diam, left + right);return Math.max(left, right) + 1;}
}

---

102. 二叉树的层序遍历

思路：使用 Deque 模拟队列数据结构，每次进队将一层节点出队，并将下一层节点进队。

class Solution {/*** 输入：root = [3,9,20,null,null,15,7]* 输出：[[3],[9,20],[15,7]]*/public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();Deque<TreeNode> queue = new LinkedList<>();if (root != null) {queue.add(root);}while (!queue.isEmpty()) {int size = queue.size(); // 当前队列中节点数量 sizeList<Integer> list = new ArrayList<>();for (int i = size; i > 0; i--) { // 循环 size 次，存储该层节点TreeNode node = queue.remove();list.add(node.val);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}res.add(list);}return res;}
}

注意：每次循环提前求出队列中节点数量，是因为如果没有提前求出 for (int i = 0; i < queue.size; i++)，由于队列的节点数量是变化的，循环结束的条件会发生变化。

---

108. 将有序数组转换为二叉搜索树

题意要求：将有序数组转换为 平衡 二叉搜索树，这里可以借鉴二分查找的思路。

  

class Solution {/*** 输入：nums = [-10,-3,0,5,9]* 输出：[0,-3,9,-10,null,5]* 解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案*/public TreeNode sortedArrayToBST(int[] nums) {return buildBST(nums, 0, nums.length - 1);}private TreeNode buildBST(int[] nums, int left, int right) {if (left > right) {return null;}int mid = left - (left - right) / 2; // 防溢出TreeNode node = new TreeNode(nums[mid]);node.left = buildBST(nums, left, mid - 1);node.right = buildBST(nums, mid + 1, right);return node;}
}

---

98. 验证二叉搜索树

思路：二叉搜索树中序遍历是递增的，因此可以利用栈辅助完成中序遍历的同时来验证是否是二叉搜索树。

class Solution {/*** 输入：root = [2,1,3]* 输出：true*/public boolean isValidBST(TreeNode root) {Deque<TreeNode> stack = new LinkedList<>();long val = Long.MIN_VALUE;TreeNode p = root;while (!stack.isEmpty() || p != null) {if (p != null) {stack.push(p);p = p.left;} else {TreeNode top = stack.pop();if (val >= top.val) {return false;}val = top.val;p = top.right;}}return true;}
}

也可使用递归的思路：

class Solution {long max = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if(root == null){return true;}if(!isValidBST(root.left)){return false;}if(root.val <= max){return false;}else{max = root.val;}return isValidBST(root.right);}
}

---

230. 二叉搜索树中第 K 小的元素

思路同上，使用栈进行中序遍历的同时，查询第 K 小的元素。

class Solution {/*** 输入：root = [3,1,4,null,2], k = 1* 输出：1*/public int kthSmallest(TreeNode root, int k) {Deque<TreeNode> stack = new LinkedList<>();TreeNode p = root;while (!stack.isEmpty() || p != null) {if (p != null) {stack.push(p);p = p.left;} else {p = stack.pop();if (--k == 0) {return p.val;}p = p.right;}}return 0;}
}

---

199. 二叉树的右视图

借鉴层序遍历算法，每次取每一层最后一个元素。

class Solution {/*** 输入: [1,2,3,null,5,null,4]* 输出: [1,3,4]*/public List<Integer> rightSideView(TreeNode root) {if (root == null) {return new ArrayList<>();}Deque<TreeNode> queue = new LinkedList<>();List<Integer> res = new ArrayList<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = size; i > 0; i--) {TreeNode node = queue.remove();if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}if (i == 1) {res.add(node.val);}}}return res;}
}

---

114. 二叉树展开为链表

思路：
① 将左子树的最右节点指向右子树的根节点；
② 将左子树接到右子树的位置；
③ 处理右子树的根节点。
一直重复上边的过程，直到新的右子树为 null。

class Solution {/*** 输入：root = [1,2,5,3,4,null,6]* 输出：[1,null,2,null,3,null,4,null,5,null,6]*/public void flatten(TreeNode root) {TreeNode p = root;while (p != null) {if (p.left != null) {TreeNode pLeft = p.left;TreeNode pLeftRight = p.left;while (pLeftRight.right != null) { // 查询左子树的最右节点pLeftRight = pLeftRight.right;}pLeftRight.right = p.right;p.right = pLeft;p.left = null;}p = p.right;}}
}

---

105. 从前序与中序遍历序列构造二叉树

思路：团体程序设计天梯赛-练习集 L2-011 玩转二叉树 (25分) 先序中序建树 思路详解

class Solution {/*** 输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]* 输出: [3,9,20,null,null,15,7]*/public TreeNode buildTree(int[] preorder, int[] inorder) { // 先序，中序return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);}/*** 先序中序构建二叉树** @param preorder 先序遍历* @param preLeft 先序左边界* @param preRight 先序右边界* @param inorder 中序遍历* @param inLeft 中序左边界* @param inRight 中序右边界* @return 根节点*/public TreeNode build(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight) {if (inLeft > inRight || preLeft > preRight) {return null;}TreeNode root = new TreeNode(preorder[preLeft]); // 先序遍历的第一个节点是根节点int rootInd = inLeft; // root 代表中序遍历数组中的根节点的索引for (int i = inLeft; i <= inRight; i++) {if (inorder[i] == preorder[preLeft]) {rootInd = i;break;}}int len = rootInd - inLeft; // 左子树的长度// 先序（根左右）：左边界+1、左边界+长度，中序（左根右）：左边界、根节点位置-1root.left = build(preorder, preLeft + 1, preLeft + len, inorder, inLeft, rootInd - 1);// 先序（根左右）：左边界+长度+1、右边界，中序（左根右）：根节点位置+1、右边界root.right = build(preorder, preLeft + len + 1, preRight, inorder, rootInd + 1, inRight);return root;}
}

---

补充：106. 从中序与后序遍历序列构造二叉树

题目链接：https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/

class Solution {/*** 输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]* 输出：[3,9,20,null,null,15,7]*/public TreeNode buildTree(int[] inorder, int[] postorder) {return build(postorder, 0, postorder.length - 1, inorder, 0, inorder.length - 1);}/*** 后序中序构建二叉树** @param postorder 后序遍历* @param postLeft 后序左边界* @param postRight 后序右边界* @param inorder 中序遍历* @param inLeft 中序左边界* @param inRight 中序右边界* @return 根节点*/private TreeNode build(int[] postorder, int postLeft, int postRight, int[] inorder, int inLeft, int inRight) {if (postLeft > postRight || inLeft > inRight) {return null;}TreeNode root = new TreeNode(postorder[postRight]);int rootInd = inLeft;for (int i = inLeft; i <= inRight; i++) {if(inorder[i] == postorder[postRight]){rootInd = i;break;}}int len = rootInd - inLeft; // 左子树节长度// 后序（左右根）：左边界、左边界+长度-1；中序（左根右）：左边界、根节点位置-1root.left = build(postorder, postLeft, postLeft + len -1, inorder, inLeft, rootInd-1);// 后序（左右根）：左边界+长度、右边界-1，中序（左根右）：根节点位置+1、右边界root.right = build(postorder, postLeft + len, postRight-1, inorder, rootInd + 1, inRight);return root;}
}

---

437. 路径总和 III

思路：以当前节点为止，每次去查看之前的的 map 集合中是否还存在目标前缀和。
    ①
   /
   ②
  /
  ③

假设目标和为 5，节点 1 的前缀和为：1，节点 3 的前缀和为: 1+2+3 = 6，那么 pre(3) - pre(1) = 5
所以从节点 1 到节点 3 之间有一条路径长度为 5。

class Solution {// key:前缀和，value:前缀和的数量（状态会恢复）Map<Long, Integer> map;/*** 输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8* 输出：3* 解释：和等于 8 的路径有 3 条*/public int pathSum(TreeNode root, int targetSum) {map = new HashMap<>();map.put(0l, 1);return backtrack(root, 0L, targetSum);}private int backtrack(TreeNode root, Long curr, int target) {if (root == null) {return 0;}int res = 0;curr += root.val;// 以当前节点为止，去查看从前的 map 集合中是否还存在目标前缀和res += map.getOrDefault(curr - target, 0);// 存储路径的原因是可能节点的前缀和存在相等的情况：//              2//             ///            0//           ///          4// 从节点 2 到节点 4 有两条路径长度等于2map.put(curr, map.getOrDefault(curr, 0) + 1);int left = backtrack(root.left, curr, target);int right = backtrack(root.right, curr, target);res += left + right;// 状态恢复map.put(curr, map.get(curr) - 1);return res;}
}

---

补充：112. 路径总和

题目链接：https://leetcode.cn/problems/path-sum/description/

class Solution {/*** 输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22* 输出：true* 解释：等于目标和的根节点到叶节点路径如上图所示*/public boolean hasPathSum(TreeNode root, int targetSum) {return backtrack(root, 0, targetSum);}private boolean backtrack(TreeNode root, int curr, int target) {if (root == null) {return false;}curr += root.val;if (root.left == null && root.right == null) {return curr == target;}boolean left = backtrack(root.left, curr, target);boolean right = backtrack(root.right, curr, target);return left || right;}
}

---

补充：113. 路径总和 II

题目链接：https://leetcode.cn/problems/path-sum-ii/description/

class Solution {List<List<Integer>> res;/*** 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22* 输出：[[5,4,11,2],[5,8,4,5]]*/public List<List<Integer>> pathSum(TreeNode root, int targetSum) {res = new ArrayList<>();backtrack(root, 0, targetSum, new ArrayList<>());return res;}private void backtrack(TreeNode root, int curr, int target, List<Integer> path) {if (root == null) {return;}curr += root.val;path.add(root.val);if (root.left == null && root.right == null && curr == target) {res.add(new ArrayList<>(path));}backtrack(root.left, curr, target, path);backtrack(root.right, curr, target, path);path.remove(path.size() - 1); // 恢复状态}
}

---

236. 二叉树的最近公共祖先

思路参考：236. 二叉树的最近公共祖先（DFS ，清晰图解）

class Solution {/*** 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1* 输出：3* 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。*/public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {return dfs(root, p, q);}private TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {if (root == null) {return null;}if (root == p || root == q) {return root;}TreeNode left = dfs(root.left, p, q);TreeNode right = dfs(root.right, p, q);if (left != null && right != null) {return root;} else if (left != null) {return left;} else if (right != null) {return right;} else {return null;}}
}

---

124. 二叉树中的最大路径和

class Solution {private int maxPath = Integer.MIN_VALUE;/*** 输入：root = [-10,9,20,null,null,15,7]* 输出：42* 解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42*/public int maxPathSum(TreeNode root) {getMaxPath(root);return maxPath;}private int getMaxPath(TreeNode root) {if (root == null) {return 0;}int leftMaxPath = Math.max(0, getMaxPath(root.left));int rightMaxPath = Math.max(0, getMaxPath(root.right));maxPath = Math.max(leftMaxPath + root.val + rightMaxPath, maxPath);return Math.max(leftMaxPath, rightMaxPath) + root.val;}
}

---

九、图论

200. 岛屿数量

class Solution {/*** 输入：grid = [*   ["1","1","1","1","0"],*   ["1","1","0","1","0"],*   ["1","1","0","0","0"],*   ["0","0","0","0","0"]* ]* 输出：1*/public int numIslands(char[][] grid) {int m = grid.length;int n = grid[0].length;int res = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == '1') {dfs(grid, i, j, m, n);res++;}}}return res;}private void dfs(char[][] grid, int x, int y, int m, int n) {if (0 <= x && x < m && 0 <= y && y < n && grid[x][y] == '1') {grid[x][y] = '0';dfs(grid, x, y - 1, m, n); // 左上右下dfs(grid, x - 1, y, m, n);dfs(grid, x, y + 1, m, n);dfs(grid, x + 1, y, m, n);}}
}

---

994. 腐烂的橘子

思路：遍历的方式参考树的层序遍历，区别在于题目刚开始的入队的节点可能有多个。

class Solution {/*** 输入：grid = [[2,1,1],[1,1,0],[0,1,1]]* 输出：4*/public int orangesRotting(int[][] grid) {int m = grid.length;int n = grid[0].length;Deque<Point> queue = new LinkedList<>();int flesh = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 2) {queue.add(new Point(i, j));}if (grid[i][j] == 1) {flesh++;}}}if (flesh == 0) {return 0;}int res = 0;int[][] dirs = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}}; // 左上右下四个方向while (!queue.isEmpty() && flesh > 0) { // 注意：如果不用 flesh 做判断，队列中还存在节点，因此还会再循环一轮int size = queue.size();res++;for (int i = size; i > 0; i--) {Point point = queue.remove();int x = point.x;int y = point.y;for (int[] dir : dirs) {int newX = x + dir[0];int newY = y + dir[1];if (0 <= newX && newX < m && 0 <= newY && newY < n && grid[newX][newY] == 1) {grid[newX][newY] = 2;flesh--;queue.add(new Point(newX, newY));}}}}return flesh == 0 ? res : -1;}class Point {int x;int y;public Point() {}public Point(int x, int y) {this.x = x;this.y = y;}}
}

---

207. 课程表

思路：拓扑排序

class Solution {/*** 输入：numCourses = 2, prerequisites = [[1,0]]* 输出：true* 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。*/public boolean canFinish(int numCourses, int[][] prerequisites) {List<List<Integer>> neighborTable = buildNeighborTable(numCourses, prerequisites);Deque<Integer> stack = new LinkedList<>(); // 用来存储入度为0的节点int count = 0; // 用来记录拓扑排序中的节点数量int[] indegree = new int[numCourses]; // 存储每个节点的入度for (int[] prerequisite : prerequisites) {indegree[prerequisite[0]]++;}for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0) {stack.push(i);}}while (!stack.isEmpty()) {Integer pop = stack.pop();count++;for (Integer ind : neighborTable.get(pop)) { // 邻接表中当前节点所关联的节点入度-1indegree[ind]--;if (indegree[ind] == 0) {stack.push(ind);}}}return count == numCourses;}private List<List<Integer>> buildNeighborTable(int numCourses, int[][] prerequisites) {List<List<Integer>> neighborTable = new ArrayList<>(numCourses);for (int i = 0; i < numCourses; i++) {neighborTable.add(new ArrayList<>());}for (int i = 0; i < prerequisites.length; i++) { // 构造邻接表neighborTable.get(prerequisites[i][1]).add(prerequisites[i][0]);}return neighborTable;}
}

---

补充：210. 课程表 II

题目链接：https://leetcode.cn/problems/course-schedule-ii/description/

class Solution {public int[] findOrder(int numCourses, int[][] prerequisites) {List<List<Integer>> neighborTable = buildNeighborTable(numCourses, prerequisites);Deque<Integer> stack = new LinkedList<>(); // 用来存储入度为0的节点int count = 0; // 用来记录拓扑排序中的节点数量int[] topologies = new int[numCourses];int[] indegree = new int[numCourses]; // 存储每个节点的入度for (int[] prerequisite : prerequisites) {indegree[prerequisite[0]]++;}for (int i = 0; i < numCourses; i++) {if (indegree[i] == 0) {stack.push(i);}}while (!stack.isEmpty()) {Integer pop = stack.pop();topologies[count++] = pop;for (Integer ind : neighborTable.get(pop)) { // 邻接表中当前节点所关联的节点入度-1indegree[ind]--;if (indegree[ind] == 0) {stack.push(ind);}}}return count == numCourses ? topologies : new int[0];}private List<List<Integer>> buildNeighborTable(int numCourses, int[][] prerequisites) {List<List<Integer>> neighborTable = new ArrayList<>(numCourses);for (int i = 0; i < numCourses; i++) {neighborTable.add(new ArrayList<>());}for (int i = 0; i < prerequisites.length; i++) { // 构造邻接表neighborTable.get(prerequisites[i][1]).add(prerequisites[i][0]);}return neighborTable;}
}

---

208. 实现 Trie (前缀树)

class Trie {class Node {Boolean isEnd;Node[] next;public Node() {this.isEnd = false;this.next = new Node[26];}}private final Node root;public Trie() {root = new Node();}public void insert(String word) {Node node = root;for (char ch : word.toCharArray()) {if (node.next[ch - 'a'] == null) {node.next[ch - 'a'] = new Node();}node = node.next[ch - 'a'];}node.isEnd = true;}public boolean search(String word) {Node node = root;for (char ch : word.toCharArray()) {if (node.next[ch - 'a'] == null) {return false;}node = node.next[ch - 'a'];}return node.isEnd;}public boolean startsWith(String prefix) {Node node = root;for (char ch : prefix.toCharArray()) {if (node.next[ch - 'a'] == null) {return false;}node = node.next[ch - 'a'];}return true;}
}/*** Your Trie object will be instantiated and called as such:* Trie obj = new Trie();* obj.insert(word);* boolean param_2 = obj.search(word);* boolean param_3 = obj.startsWith(prefix);*/

---

十、回溯

46. 全排列

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

class Solution {/*** 输入：nums = [1,2,3]* 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]*/public List<List<Integer>> permute(int[] nums) {List<List<Integer>> res = new ArrayList<>();int len = nums.length;boolean[] visited = new boolean[len];dfs(res, nums, visited, new ArrayList<>());return res;}private void dfs(List<List<Integer>> res, int[] nums, boolean[] visited, List<Integer> list) {if (list.size() == nums.length) {res.add(new ArrayList<>(list));return;}for (int i = 0; i < nums.length; i++) {if (!visited[i]) {list.add(nums[i]);visited[i] = true;dfs(res, nums, visited, list);list.remove(list.size() - 1);visited[i] = false;}}}
}

---

补充：47. 全排列 II

题目链接：https://leetcode.cn/problems/permutations-ii/

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

class Solution {/*** 输入：nums = [1,1,2]* 输出：[[1,1,2],[1,2,1],[2,1,1]]*/public List<List<Integer>> permuteUnique(int[] nums) {List<List<Integer>> res = new ArrayList<>();Arrays.sort(nums); // 排序boolean[] visited = new boolean[nums.length];backtrack(visited, nums, new ArrayList<>(), res);return res;}private void backtrack(boolean[] visited, int[] nums, List<Integer> list, List<List<Integer>> res) {if (list.size() == nums.length) {res.add(new ArrayList<>(list));return;}for (int i = 0; i < nums.length; i++) {if (!visited[i]) {if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == false) { // 剪枝continue;}visited[i] = true;list.add(nums[i]);backtrack(visited, nums, list, res);list.remove(list.size() - 1);visited[i] = false;}}}
}

---

78. 子集

class Solution {/*** 输入：nums = [1,2,3] * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]*/public List<List<Integer>> subsets(int[] nums) {List<List<Integer>> res = new ArrayList<>();int len = nums.length;boolean[] visited = new boolean[len];dfs(nums, 0, new ArrayList<>(), res);return res;}private void dfs(int[] nums, int ind, List<Integer> list, List<List<Integer>> res) {if (ind >= nums.length) {res.add(new ArrayList<>(list));return;}list.add(nums[ind]);dfs(nums, ind + 1, list, res);list.remove(list.size() - 1);dfs(nums, ind + 1, list, res);}
}

---

17. 电话号码的字母组合

class Solution {Map<Character, String> map = new HashMap<>();String digits;/*** 输入：digits = "23"* 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]*/public List<String> letterCombinations(String digits) {if (digits.length() == 0) {return new ArrayList<>();}map.put('2', "abc");map.put('3', "def");map.put('4', "ghi");map.put('5', "jkl");map.put('6', "mno");map.put('7', "pqrs");map.put('8', "tuv");map.put('9', "wxyz");this.digits = digits;List<String> res = new ArrayList<>();backtrack(0, new StringBuilder(), res);return res;}private void backtrack(int ind, StringBuilder builder, List<String> res) {if (ind == digits.length()) {res.add(new String(builder));return;}String words = map.get(digits.charAt(ind));for (char ch : words.toCharArray()) {builder.append(ch);backtrack(ind+1, builder, res);builder.deleteCharAt(builder.length() - 1);}}
}

---

39. 组合总和

题目： 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

class Solution {int[] candidates;/*** 输入：candidates = [2,3,6,7], target = 7* 输出：[[2,2,3],[7]]* 解释：* 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。* 7 也是一个候选， 7 = 7 。* 仅有这两种组合。*/public List<List<Integer>> combinationSum(int[] candidates, int target) {this.candidates = candidates;List<List<Integer>> res = new ArrayList<>();Arrays.sort(candidates);backtrack(target, 0, new ArrayList<>(), res);return res;}private void backtrack(int target, int ind, List<Integer> temp, List<List<Integer>> res) {if (target < 0) {return;}if (target == 0) {res.add(new ArrayList<>(temp));return;}for (int i = ind; i < candidates.length; i++) {if (target - candidates[i] < 0) {break;}temp.add(candidates[i]);backtrack(target - candidates[i], i, temp, res);temp.remove(temp.size() - 1);}}
}

---

补充：40. 组合总和 II

题目链接：https://leetcode.cn/problems/combination-sum-ii/description/

与上道题目不同的是，解集不能包含重复的组合， 参考：全排列 II：

class Solution {int[] candidates;/*** 输入: candidates = [10,1,2,7,6,1,5], target = 8,* 输出: [[1,1,6],[1,2,5],[1,7],[2,6]]*/public List<List<Integer>> combinationSum2(int[] candidates, int target) {this.candidates = candidates;List<List<Integer>> res = new ArrayList<>();boolean[] visited = new boolean[candidates.length];Arrays.sort(candidates);backtrack(target, 0, visited, new ArrayList<>(), res);return res;}private void backtrack(int target, int ind, boolean[] visited, List<Integer> list, List<List<Integer>> res) {if (target < 0) {return;}if (target == 0) {res.add(new ArrayList<>(list));return;}for (int i = ind; i < candidates.length; i++) {if (!visited[i]) {if (target - candidates[i] < 0) {break;}if (i != 0 && candidates[i - 1] == candidates[i] && !visited[i - 1]) {continue;}list.add(candidates[i]);visited[i] = true;backtrack(target - candidates[i], i + 1, visited, list, res);visited[i] = false;list.remove(list.size() - 1);}}}
}

---

补充：216. 组合总和 III

题目链接：https://leetcode.cn/problems/combination-sum-iii/description/

题目：找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：
① 只使用数字 1 到 9
② 每个数字最多使用一次
③ 返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

class Solution {List<List<Integer>> res;int size;/*** 输入: k = 3, n = 7* 输出: [[1,2,4]]* 解释: 1 + 2 + 4 = 7 没有其他符合的组合了。*/public List<List<Integer>> combinationSum3(int k, int n) {this.res = new ArrayList<>();this.size = k;backtrack(1, n, new ArrayList<>());return res;}private void backtrack(int ind, int target, List<Integer> list) {if (target == 0) {if (size == list.size()) {res.add(new ArrayList<>(list));}return;}for (int i = ind; i < 10; i++) {if (target - i < 0) {break;}list.add(i);backtrack(i + 1, target - i, list);list.remove(list.size() - 1);}}
}

---

22. 括号生成

思路：每次优先选左括号，然后再选右括号。

class Solution {/*** 输入：n = 3* 输出：["((()))","(()())","(())()","()(())","()()()"]*/public List<String> generateParenthesis(int n) {List<String> res = new ArrayList<>();backtrack(n, n, new StringBuilder(), res);return res;}private void backtrack(int left, int right, StringBuilder builder, List<String> res) {if (left > right) { // 左括号少，剪枝return;}if (left == 0 && right == 0) {res.add(builder.toString());return;}if (left != 0) { // 优先选左builder.append('(');backtrack(left - 1, right, builder, res);builder.deleteCharAt(builder.length() - 1);}builder.append(')');backtrack(left, right - 1, builder, res);builder.deleteCharAt(builder.length() - 1);}
}

---

79. 单词搜索

class Solution {/*** 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"* 输出：true*/public boolean exist(char[][] board, String word) {int m = board.length;int n = board[0].length;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (board[i][j] == word.charAt(0) && dfs(word, i, j, 0, board)) {return true;}}}return false;}private boolean dfs(String word, int x, int y, int ind, char[][] board) {if (ind >= word.length()) {return true;}if (0 <= x && x < board.length && 0 <= y && y < board[0].length && board[x][y] == word.charAt(ind)&& board[x][y] != '\0') {char ch = board[x][y];board[x][y] = '\0';boolean left = dfs(word, x, y - 1, ind + 1, board); // 左上右下boolean up = dfs(word, x - 1, y, ind + 1, board);boolean right = dfs(word, x, y + 1, ind + 1, board);boolean down = dfs(word, x + 1, y, ind + 1, board);board[x][y] = ch;return left || up || right || down;}return false;}
}

---

131. 分割回文串

class Solution {List<List<String>> res;public List<List<String>> partition(String s) {res = new ArrayList<>();backtrack(s, 0, new ArrayList<>());return res;}private void backtrack(String s, int ind, List<String> list) {if (ind >= s.length()) {res.add(new ArrayList<>(list));return;}for (int i = ind; i < s.length(); i++) {if (isPalindrome(s, ind, i)) {list.add(s.substring(ind, i + 1));backtrack(s, i + 1, list);list.remove(list.size() - 1);}}}private boolean isPalindrome(String s, int start, int end) {while (start <= end) {if (s.charAt(start) != s.charAt(end)) {return false;}start++;end--;}return true;}
}

---

51. N 皇后

class Solution {/*** 输入：n = 4* 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]* 解释：如上图所示，4 皇后问题存在两个不同的解法。*/public List<List<String>> solveNQueens(int n) {List<List<String>> res = new ArrayList<>();int[] queenCols = new int[n]; // {1,3,0,2} 存储第i行的皇后在第 queenCols.get(i) 列dfs(0, n, queenCols, res);return res;}private List<String> convert(int[] queenCols, int n) {List<String> solution = new ArrayList<>();// {1,3,0,2} -> [".Q..","...Q","Q...","..Q."],for (Integer col : queenCols) {char[] temp = new char[n];Arrays.fill(temp, '.');temp[col] = 'Q';solution.add(new String(temp));}return solution;}private void dfs(int row, int n, int[] queenCols, List<List<String>> res) {if (row == n) {res.add(convert(queenCols, n));return;}for (int col = 0; col < n; col++) { // 对当前行的每一列进行遍历if (!isValid(queenCols, row, col)) {continue;}queenCols[row] = col;dfs(row + 1, n, queenCols, res);queenCols[row] = -1;}}private boolean isValid(int[] queenCols, int row, int col) {for (int i = 0; i < row; i++) {if (queenCols[i] == col || row - i == col - queenCols[i] || row - i == queenCols[i] - col) {// 同一列；同'\'方向，“行-皇后所在行 == 列-皇后所在列”；同'/'方向，“行-皇后所在行 == 皇后所在列-列”return false;}}return true;}
}

以上解决方案也适用于：
面试题 08.12. 八皇后：https://leetcode.cn/problems/eight-queens-lcci/description/
52. N 皇后 II：https://leetcode.cn/problems/n-queens-ii/description/