递归算法题（1）
递归：
1. 汉诺塔问题
题目描述：
算法思路：
1. 如何解决
2. 为什么用递归
当大问题可以拆分成相同类型的子问题，而子问题又能拆分成相同类型的子问题，即可使用递归
3. 如何编写递归的代码
(1) 重复子问题 -> 函数头
本题中：将 A 柱子上的一堆盘子，借助 B 柱子，转移到 C 柱子 转换为 void dfs(A, B, C, int n)
其中 n 表示要转移的盘子数量
(2) 只关心某一个子问题在做什么 -> 函数体
dfs(A, C, B, n-1); 对应上面图中步骤 ①
C.add(A.remove(A.size() - 1)); 对应上面图中步骤 ②
dfs(B, A, C, n-1); 对应上面图中步骤 ③
(3) 递归的出口
当 n == 1 时，C.add(A.remove(A.size() - 1));
代码实现：
class Solution {public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {int n = A.size();dfs(A, B, C, n); // 将 A 上盘子借助 B 转移到 C 上System.out.println(C);}private void dfs(List<Integer> A, List<Integer> B, List<Integer> C, int n) {if (n == 1) { // 当 A 上就一个盘子时，直接转移到 C 上C.add(A.remove(A.size() - 1));return;}dfs(A, C, B, n - 1); // 将 A 上盘子借助 C 转移到 B 上C.add(A.remove(A.size() - 1)); // 将 A 上盘子直接转移到 C 上dfs(B, A, C, n - 1); // 将 B 上盘子借助 A 转移到 C 上}
}2. 合并两个有序链表
题目描述：
解法一：迭代
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1 == null && list2 == null) {return null;}if (list1 == null && list2 != null) {return list2;}if (list1 != null && list2 == null) {return list1;}ListNode head = new ListNode();ListNode ret = head;while (list1 != null && list2 != null) {if (list1.val < list2.val) {ret.next = list1;list1 = list1.next;} else {ret.next = list2;list2 = list2.next;}ret = ret.next;}if (list1 == null && list2 != null) {ret.next = list2;}if (list1 != null && list2 == null) {ret.next = list1;}return head.next;}
}解法二：递归
算法思路：
代码实现：
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) return l2;if (l2 == null) return l1;if (l1.val <= l2.val) {l1.next = mergeTwoLists(l1.next, l2);return l1;} else {l2.next = mergeTwoLists(l1, l2.next);return l2;}}
}3. 反转链表
题目描述：
解法一：栈 + 循环
class Solution {public ListNode reverseList(ListNode head) {if (head == null) return head;Stack<ListNode> stack = new Stack<>();// 将链表中节点全部添加到栈中while (head != null) {stack.push(head);head = head.next;}ListNode node = stack.pop();ListNode newHead = node;// 栈中节点全部出栈，重新连接成一个新链表while (!stack.empty()) {node.next = stack.pop();node = node.next;}// 最后一个节点就是反转前的头节点，需将其next置为null，否则会成环node.next = null;return newHead;}
}解法二：递归
思路
代码实现：
class Solution {public ListNode reverseList(ListNode head) {// 递归出口if (head == null || head.next == null) return head;// 递归，逆序后续节点，且返回逆序后的头节点ListNode newHead = reverseList(head.next);// 逆序操作head.next.next = head;head.next = null;return newHead;}
}4. 两两交换链表中的节点
题目描述：
解法一：迭代
代码实现：
class Solution {public ListNode swapPairs(ListNode head) {ListNode dummyHead = new ListNode(1);dummyHead.next = head;ListNode temp = dummyHead;while (temp.next != null && temp.next.next != null) {ListNode node1 = temp.next;ListNode node2 = temp.next.next;temp.next = node2;node1.next = node2.next;node2.next = node1;temp = node1;}return dummyHead.next;}
}解法二：递归版
算法思路：（宏观看待递归）
- 递归函数的含义：交给函数一个链表，将这个链表两两交换一下，然后返回交换后的头节点
- 函数体：先处理第二个节点以后的链表，然后再把前两个节点交换一下，连接上后面处理好的链表
- 递归出口：当前节点为空或当前只剩一个节点时，不用交换，直接返回
代码实现：
class Solution {public ListNode swapPairs(ListNode head) {// 若传入节点为空，或只剩一个节点，则无需交换if(head == null || head.next == null) return head;ListNode tmp = swapPairs(head.next.next);ListNode ret = head.next;ret.next = head;head.next = tmp;return ret;}
}5. Pow(x, n)
题目描述：
解法一：暴力循环（会超时）
class Solution {public double myPow(double x, int n) {double sum = 1;if (n >= 0) {for (int i = 0; i < n; i++) {sum *= x;}} else {n *= -1;for (int i = 0; i < n; i++) {sum *= 1 / x;}}return sum;}
}解法二：快速幂 + 递归
算法思路：
1. 相同子问题 -> 函数头：int pow(x, n)
2. 只关心每一个子问题做了什么 -> 函数体：
tmp = pow(x, n / 2);
return n % 2 == 0 ? tmp * tmp : tmp * tmp * x;
3. 递归出口：if (n == 0) return 1;
tip：细节问题
1. n 有可能为负数：，让 1.0 除 x 的 -n 次方即可
2. n 可能是 ：将 n 改为 long 类型接收
代码实现：
class Solution {public double myPow(double x, int n) {long N = n; // -2^31 <= n，防止 int 存不下// 处理 n 可能为负数的情况return (N < 0) ? (1.0 / pow(x, -N)) : (pow(x, N));}private double pow(double x, long N) {if (N == 0) return 1.0;double tmp = pow(x, N / 2);// 处理 n 可能为 奇数 的情况return N % 2 == 0 ? tmp * tmp : tmp * tmp * x;}
}二叉树中的深搜
深度优先遍历（DFS，全称 Depth First Traversal），是树或图这样的数据结构中常用的一种遍历算法，这个算法会尽可能深的搜索树或图的分支，直到一条路径上的所有节点都被遍历完毕，然后再回溯到上一层，继续找一条路遍历
6. 计算布尔二叉树的值
题目描述：
解法：递归
宏观看待递归：
函数头：每次递归都是一棵子二叉树，将其头节点传入
dfs(root)
函数体：通过递归得到当前根节点的左右子树的 boolean 值
boolean left = dfs(root.left)
boolean right = dfs(root.right)
递归出口：到达叶子节点直接返回叶子节点的 boolean 值
if (root.left == null) return true or false
代码实现：
class Solution {public boolean evaluateTree(TreeNode root) {// 递归出口，到叶子节点返回其值代表的 booleanif (root.left == null) return root.val == 1;// 递归求得其左右子树的 boolean 值boolean left = evaluateTree(root.left);boolean right = evaluateTree(root.right);// 根据头节点的值，判断其运算符为 or 还是 andreturn root.val == 2 ? left | right : left & right;}
}7. 求根节点到叶节点数字之和
题目描述：
算法思路：
递归问题第一步：找相同子问题，如下图：
当位于节点 5 时
①：接收当前节点根节点的值 * 10 + 当前的 5
②：左子树递归
③：右子树递归
④：计算左右子树返回值之和
综上得出：
函数头：int dfs(root, preSum)
函数体：① ② ③ ④
递归出口：到达叶子节点返回（tip：该步骤放在 ① 和 ② 之间进行，因为叶子节点的值也需要计算）
代码实现：
class Solution {public int sumNumbers(TreeNode root) {return dfs(root, 0);}private int dfs(TreeNode root, int preSum) {// 若当前节点为空，即当前节点值为 0if (root == null) return 0;// 到达该节点后的数字之和等于根节点的值乘 10 + 当前节点值preSum = preSum * 10 + root.val;// 递归出口if (root.left == null && root.right == null) return preSum;// 计算左右子树的数字之和int ret = 0;ret += dfs(root.left, preSum);ret += dfs(root.right, preSum);return ret;}
}8. 二叉树剪枝
题目描述：
代码实现：
class Solution {public TreeNode pruneTree(TreeNode root) {if (root == null) return null;// 处理左右子树root.left = pruneTree(root.left);root.right = pruneTree(root.right);// 判断当前节点是否需要剪枝if (root.val == 0 && root.left == null && root.right == null) return null;else return root;}
}9. 验证二叉搜索树
题目描述：
算法思路：
利用二叉搜索树的性质：二叉搜索树的中序遍历结果是一个严格递增的序列
我们可以初始化一个无穷小的 全局变量，用来记录中序遍历过程中的 前驱节点，这样就可以在中序遍历的过程中，先判断是否和前驱节点构成递增序列，然后修改前驱节点为当前节点，传入下一层的递归中
tip：由于题目中的取值范围：，因此无穷小不能使用 Integer.MIN_VALUE，而是使用 Long.MIN_VALUE
实现代码：
class Solution {// 全局变量用于和当前值进行比较，利用二叉搜索树的性质：二叉搜索树的中序遍历结果是一个有序的序列long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) return true;boolean left = isValidBST(root.left);// 遍历当前根节点boolean cur = prev < root.val ? true : false;prev = root.val; // 比较完后别忘了将 prev 变为 当前根节点的值boolean right = isValidBST(root.right);return left && cur && right;}
}优化：加入剪枝操作，可减少无用的递归操作
class Solution {// 全局变量用于和当前值进行比较，利用二叉搜索树的性质：二叉搜索树的中序遍历结果是一个有序的序列long prev = Long.MIN_VALUE;public boolean isValidBST(TreeNode root) {if (root == null) return true;boolean left = isValidBST(root.left);// 剪枝if (left == false) return false;// 遍历当前根节点boolean cur = prev < root.val ? true : false;// 剪枝if (cur == false) return false;prev = root.val; // 比较完后别忘了将 prev 变为 当前根节点的值boolean right = isValidBST(root.right);return left && cur && right;}
}10. 二叉搜索树中第 K 小的元素
题目描述：
算法思路：
两个全局变量 + 中序遍历
由于二叉搜索树的中序遍历具有递增性质，因此利用中序遍历，先令 count = k，每遍历一个节点 count--，当 count 等于 0 时，将当前 root.val 赋值给 ret，此时 ret 就是所求值
代码实现：
class Solution {// 定义两个全局变量，一个用来存值，一个用来计数int ret;int count;public int kthSmallest(TreeNode root, int k) {count = k;dfs(root);return ret;}private void dfs(TreeNode root) {// 递归出口 + 剪枝优化（此处只优化了左子树）if (root == null || count == 0) return;dfs(root.left);count--;if (count == 0) ret = root.val;// 剪枝优化右子树if (count <= 0) return;dfs(root.right);}
}11. 二叉树的所有路径
题目描述：
算法原理：
回溯 -> “恢复现场”（题目中出现回溯才要去 “恢复现场”，而不是出现 “恢复现场” 才去使用回溯）
只要出现 递归，必然会用到 回溯，也就是一定会 “恢复现场”，当变量通过参数传递时，可能就自动 “恢复现场” 了，但若用到全局变量，必然伴随手动 “恢复现场”
算法思路：
如下图例：
当我们使用两个全局变量 ret 和 path 时
第（1）步将 path 转为 1->，第（2）步将 path 转为 1->2->，第（3）步将 path 转为 1->2->4
到第（4）步时就需要将 4 去掉，第（5）步就需要将 2-> 去掉，这样 “恢复现场” 非常麻烦
因此，我们将 path 当作参数传递（函数头：void dfs (root, path)），让其在传递过程中自动完成 “恢复现场”
函数体：
- if (root == 叶子节点) 将当前节点值拼接到 ret 上，并返回
- if (root != 叶子节点) 则在将值拼接到 ret 的基础上再拼接一个 ->
递归出口：if (root == null) return;
tip：此处可以加入剪枝操作，若是定义递归出口，则是进入叶子节点的左子树检测到为 null，则返回；若是加上剪枝操作，则是直接不进入叶子节点的左右子树
代码实现：
class Solution {List<String> ret; // 全局变量，把每一条路径组成的字符串都存到该 list 中public List<String> binaryTreePaths(TreeNode root) {ret = new ArrayList<>();dfs(root, new StringBuffer()); // 使用 StringBuffer 来做字符串拼接操作return ret;}private void dfs (TreeNode root, StringBuffer _path) {// 此处的 _path 相当于一个全局变量，不能直接修改它// 因此每次递归都新建一个 path，所有的操作都在 path 中进行，不会影响到原来的 _pathStringBuffer path = new StringBuffer(_path);// 无论是叶子节点还是非叶子节点，其中的值都是需要拼接到 ret 中的path.append(Integer.toString(root.val));if (root.left == null && root.right == null) {// 若当前节点是叶子节点，则将 path 直接添加到 ret 中，此次递归结束，直接返回ret.add(path.toString());return;}// 走到这说明不是叶子节点，将 -> 添加到 ret 中path.append("->");// 剪枝操作，只有当左右子树不为空，才会进入递归// 写了这个剪枝操作后，就不需要定义递归出口了if (root.left != null) dfs(root.left, path);if (root.right != null) dfs(root.right, path);}
}穷举 VS 暴搜 VS 深搜 VS 回溯 VS 剪枝
12. 全排列
题目描述：
算法思路：穷尽 - 枚举
分为两步：
1. 画出决策树，越详细越好
2. 设计代码
全局变量：
List<List<Integer>> ret; // 记录全排列
List<Integer> path; // 记录在本次排列中的数字
boolean[ ] check; // （剪枝操作）标记本次排列中的数字是否已被使用，false 表示未被使用
dfs 函数：仅需关心 某一个节点 在干什么事情
每一个节点要做的事：遍历 nums，将未被使用的数字添加到 path 中
细节问题：
回溯：
- 将 path 最后一个数删掉
- 将该数的 check 设为 false
剪枝：check 操作将状态为 true 的分支剪掉
递归出口：当 path 长度等于 nums 长度时，本次递归结束
代码实现：
class Solution {List<List<Integer>> ret; // 记录全排列List<Integer> path; // 记录在本次排列中的数字boolean[] check; // （剪枝）标记本次排列中改下标处数字是否已被使用，false 表示未被使用public List<List<Integer>> permute(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs (nums);return ret;}// 每一个节点都要做的事情：将 nums 遍历一遍，将未被使用的数字添加到 path 中private void dfs (int[] nums) {// 递归出口if (nums.length == path.size()) { // 当 path 的长度等于 nums 长度时，说明 nums 中的所有数都已被使用ret.add(new ArrayList<>(path)); // 将该种排列添加到 ret 中return;}for (int i = 0; i < nums.length; i++) {if (check[i] == false) { // 若当前数未被使用path.add(nums[i]); // 则将该数添加到 path 中check[i] = true; // 并将其状态设为 truedfs (nums);// 回溯操作：1.将 path 最后一个数删掉；2.将该数的 check 设为 falsepath.remove(path.size() - 1);check[i] = false;}}}
}13. 子集
题目描述：
解法一：
算法思路：
1. 决策树
每一个节点都要选择是否要将当前值加入到子集元素中
2. 设计代码
全局变量
List<List<Integer>> ret; // 记录所有子集 List<Integer> path; // 标记路径，记录单个子集
函数头：dfs(int[ ] nums, int i)
函数体：
若选择当前下标处值为子集元素，则将其添加到 path 中，然后进入 i+1 递归，递归结束后，恢复现场
若不选择，则直接进入 i+1 递归
细节问题：
本题无剪枝
回溯：函数体中的 恢复现场操作
递归出口：当 i == nums.length 时，说明已经经过了叶子节点，当前 path 中的值即为 子集之一
代码实现：
class Solution {List<List<Integer>> ret; // 记录所有子集List<Integer> path; // 标记路径，记录单个子集public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs(nums, 0);return ret;}private void dfs (int[] nums, int i) {if (i == nums.length) { // 当 i 等于数组长度时，说明已经递归完毕，将 path 添加到 ret 中，返回即可ret.add (new ArrayList<>(path));return;}// 若不选当前 i 下标值作为子集中元素，直接 i+1 跳过，进入下一次递归dfs(nums, i + 1);// 选择当前 i 下标作为子集中元素，将其添加到 path 中// 然后进入 i+1 的递归// 递归完成后，在将 path 中的最后一个元素去掉（恢复现场）path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1);}
}解法二：
算法思路：
1. 决策树
该解法是直接将数组分开，每个节点都是一个子集
2. 设计代码
全局变量
List<List<Integer>> ret; // 记录所有子集 List<Integer> path; // 标记路径，记录单个子集
函数头：dfs(nums, pos)，pos 表示当前已经递归到的下标
函数体：
从 pos 位置开始的 for 循环，将当前位置元素添加到 path 中，并进入 pos+1 递归，递归结束后 恢复现场
细节问题：
回溯：函数体中递归结束后 恢复现场
剪枝：本题无剪枝
递归出口：因为每一个节点都是一个子集，因此每次递归开始都要将 path 添加到 ret 中
代码实现：
class Solution {List<List<Integer>> ret;List<Integer> path;public List<List<Integer>> subsets(int[] nums) {ret = new ArrayList<>();path = new ArrayList<>();dfs (nums, 0);return ret;}private void dfs (int[] nums, int pos) {// 每一个节点都是一个 子集ret.add(new ArrayList<>(path));// 将当前 i 下标处元素添加到 path，并让 i+1 后进入下一个递归for (int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs (nums, i + 1);// 递归结束后要 恢复现场path.remove(path.size() - 1);}}
}14. 找出所有子集的异或总和再求和
题目描述：
算法思路：
和上面 子集 题目一模一样，需要注意的是 异或运算的消消乐（对同一个数异或两次，值不变，以此来 恢复现场）
代码实现：
class Solution {int sum; // 记录总和int path; // 记录当前子集的异或和public int subsetXORSum(int[] nums) {dfs (nums, 0);return sum;}private void dfs (int[] nums, int pos) {sum += path;for (int i = pos; i < nums.length; i++) {path ^= nums[i];dfs(nums, i+1);path ^= nums[i]; // 恢复现场}}
}15. 全排列 II
题目描述：
算法思路：
如上图，和全排列的区别就是，该题中有重复元素，因此需要考虑剪枝
通过上图可以得出有两种情况需要剪枝：
- 同一个节点的所有分支中，相同的元素只能出现一次
- 同一个数只能使用一次（使用 check 做标记，false 表示未被使用）
从而可以通过两个方面来考虑题目：
1. 只关心 “不合法” 的分支，当其符合以下判断条件时，直接 continue
check[i] == true 当该数已被使用时
或者 nums[i] == nums[i - 1] 在同一个节点中的数重复了，比如上图中第一层的 3 个 1，每一个 1 都作为一次子集开头的话，会重复很多；在此基础上，为防止 i 越界，还需满足 i != 0；再在此基础上 nums[i - 1] 必须是未被使用的状态，若状态为 true，则说明其在上一层被使用了，那当前 nums[i] 就可以正常使用了（比如第一层中的第 3 个 1）。
总结：check[i] == true || (i != 0 && nums[i] == nums[i-1] && check[i-1] == false)
2. 只关心 “合法” 的分支，当满足以下判断条件时，进入递归
check[i] == false 该数未被使用
并且 i == 0 说明是第一个数，直接用；或者 nums[i] != nums[i-1] 当前数和前一个数不一致，想要使用该条件，数组必须有序；或者 当前数和前一个数相等，但是前一个数的状态为 true，已被使用了
总结：check[i] == false &&(i == 0 || nums[i] != nums[i-1] || check[i-1] == true)
代码实现：
class Solution {List<List<Integer>> ret; // 记录结果List<Integer> path; // 记录递归结果boolean[] check;public List<List<Integer>> permuteUnique(int[] nums) {// 排序数组Arrays.sort(nums);ret = new ArrayList<>();path = new ArrayList<>();check = new boolean[nums.length];dfs(nums, 0);return ret;}private void dfs(int[] nums, int pos) {if (path.size() == nums.length) {ret.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {// 剪枝if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {path.add(nums[i]);check[i] = true;dfs(nums, i+1);// 回溯 -> 恢复现场path.remove(path.size() - 1);check[i] = false;}}}
}16. 电话号码的字母组合
题目描述：
算法思路：
决策树：
每个位置可选择的字符与其他位置不冲突，因此不需要标记已经出现的字符，只需将每个数字对应的字符依次填入字符串中进行递归，递归完再进行回溯即可
还需设计一个数字与字符串的映射关系，有三种方式：
1. 使用 HashMap
Map<Character, String> phoneMap = new HashMap<Character, String>() {{put('2', "abc");put('3', "def");put('4', "ghi");put('5', "jkl");put('6', "mno");put('7', "pqrs");put('8', "tuv");put('9', "wxyz");}};2. 使用 switch case
3. 使用 字符串数组（下面使用该方法）
递归函数设计：
List<String> ret; // 记录最终结果
StringBuffer path; // 记录每一个组合
函数头：dfs(String digits, int pos); // pos 表示当前要从那个元素开始处理
细节问题：
回溯，在每一次递归结束后执行恢复现场操作
递归出口，当 pos 等于 digits 长度时，将 path 添加到 ret 中，return 结束本次递归
代码实现：
class Solution {String[] str = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};List<String> ret;StringBuffer path;public List<String> letterCombinations(String digits) {ret = new ArrayList<>();path = new StringBuffer();if (digits.length() == 0) return ret;dfs(digits, 0);return ret;}private void dfs (String digits, int pos) {if (pos == digits.length()) {ret.add(path.toString());return;}// 从 str 中拿对应字符串// digits.charAt(pos) - '0' 当前字符 减 字符0 得到对应下标位置// 在 str 中找到该下标对应的字符串 赋值给 curString cur = str[digits.charAt(pos) - '0'];for (int i = 0; i < cur.length(); i++) {path.append(cur.charAt(i));dfs(digits, pos+1);path.deleteCharAt(path.length() - 1);}}
}17. 括号生成
题目描述：
算法思路：
要想是有效的括号组合，需要有以下两个人前提：
- 左括号数量 = 右括号数量
- 从头开始的任意一个子串中，左括号数量 >= 右括号数量
决策树：
使用全局变量解决该问题，用到的全局变量有：
left：左括号数量
right：右括号数量
n：需生成的括号对数
path：每条路径生成的括号子串
ret：所有可能的并且 有效的 括号组合
函数头：dfs()，不用传任何参数，也无需返回值
递归出口：当右括号数量等于 n 时，本次递归结束
代码实现：
class Solution {int left, right, n;List<String> ret;StringBuffer path;public List<String> generateParenthesis(int _n) {n = _n;ret = new ArrayList<>();path = new StringBuffer();dfs();return ret;}public void dfs() {if (right == n) {ret.add(path.toString());return;}// 添加左括号if (left < n) {path.append('('); left++;dfs();// 下面两步是恢复现场path.deleteCharAt(path.length() - 1); left--;}// 添加右括号if (right < left) {path.append(')');right++;dfs();// 恢复现场path.deleteCharAt(path.length() - 1);right--;}}
}18. 组合
题目描述：
算法思路：
画出决策树，需要注意的是，每次都从该节点的下一个节点递归，由此完成不重复的问题
代码实现：
class Solution {List<List<Integer>> ret;List<Integer> path;int n, k;public List<List<Integer>> combine(int _n, int _k) {n = _n; k = _k;ret = new ArrayList<>();path = new ArrayList<>();dfs(1);return ret;}private void dfs(int pos) {if (path.size() == k) {ret.add(new ArrayList<>(path));return;}for(int i = pos; i <= n; i++) {path.add(i);dfs(i + 1); // 每次从下一个节点开始，相当于剪枝path.remove(path.size() - 1);}}
}19. 目标和
题目描述：
算法思路：暴搜、深搜、回溯
代码实现：
1. 使用全局变量 sum 记录当前路径上数的运算结果
// 使用全局变量
class Solution {int count; // 记录运算结果等于 target 的数目int t; // 等于 target，相当于将其变为全局变量int sum; // 记录当前所有数的运算结果public int findTargetSumWays(int[] nums, int target) {count = 0;t = target;sum = 0;dfs(nums, 0); // 第二个参数是告诉递归，当前应该从那个位置开始计算return count;}private void dfs (int[] nums, int pos) {if (pos == nums.length) {if (sum == t) count++;return;}// 加法sum += nums[pos];dfs(nums, pos + 1);sum -= nums[pos]; // 恢复现场// 减法sum -= nums[pos];dfs(nums, pos + 1);sum += nums[pos]; // 恢复现场}
}2. 使用参数 sum 记录当前路径上数的运算结果
class Solution {int count; // 记录运算结果等于 target 的数目int t; // 等于 target，相当于将其变为全局变量public int findTargetSumWays(int[] nums, int target) {count = 0;t = target;dfs(nums, 0, 0); // 第二个参数是告诉递归，当前应该从那个位置开始计算return count;}private void dfs (int[] nums, int pos, int sum) {if (pos == nums.length) {if (sum == t) count++;return;}// 加法dfs(nums, pos + 1, sum + nums[pos]);// 减法dfs(nums, pos + 1, sum - nums[pos]);}
}20. 组合总和
题目描述：
解法一算法思路：
ret：记录最终结果
path：记录本次递归选择了哪些数
sum：当前路径数字的运算和
pos：从 pos 位置的数字开始运算
由于同一个数字可以无限重复，所以每次递归都是从当前数字开始运算，而非下一个数字
递归出口：当 sum == target 时，说明当前 path 中的数字相加是符合结果的，将其添加到 ret 中，并返回；若 sum > target 活着 pos 已经超出了 candidates.length，则说明该路径不符合条件，直接 return 即可
代码实现：
class Solution {List<List<Integer>> ret; // 记录最终结果List<Integer> path; // 记录本次递归选择了哪些数int aim; // 赋值 target，当作全局变量使用public List<List<Integer>> combinationSum(int[] candidates, int target) {ret = new ArrayList<>();path = new ArrayList<>();aim = target;dfs(candidates, 0, 0);return ret;}// pos 表示当前从哪个数字位置开始运算，sum 表示当前路径运算和public void dfs(int[] candidates, int pos, int sum) {if (sum == aim) {ret.add(new ArrayList<>(path));return;}if (sum > aim || pos == candidates.length) return;for (int i = pos; i < candidates.length; i++) {path.add(candidates[i]);dfs(candidates, i, sum + candidates[i]);path.remove(path.size() - 1);}}
}解法二算法思路：
选择当前下标数字可以使用几次，从 0 次开始，循环条件设置为不能超过 target，当该节点全部走完后，再恢复现场
代码实现：
class Solution {List<List<Integer>> ret; // 记录最终结果List<Integer> path; // 记录本次递归选择了哪些数int aim; // 赋值 target，当作全局变量使用public List<List<Integer>> combinationSum(int[] candidates, int target) {ret = new ArrayList<>();path = new ArrayList<>();aim = target;dfs(candidates, 0, 0);return ret;}// pos 表示当前从哪个数字位置开始运算，sum 表示当前路径运算和public void dfs(int[] candidates, int pos, int sum) {if (sum == aim) {ret.add(new ArrayList<>(path));return;}if (sum > aim || pos == candidates.length) return;// 枚举 nums[pos] 使用了多少个for(int k = 0; k * candidates[pos] + sum <= aim; k++) {if (k != 0) path.add(candidates[pos]);dfs(candidates, pos + 1, sum + k * candidates[pos]);}// 恢复现场for(int k = 1; k * candidates[pos] + sum <= aim; k++) {path.remove(path.size() - 1);}}
}