💕"对相爱的人来说，对方的心意，才是最好的房子。"💕
作者：Lvzi
文章主要内容：算法系列–递归,回溯,剪枝的综合应用(2)
大家好,今天为大家带来的是
算法系列--递归,回溯,剪枝的综合应用(2)
一.括号⽣成
题目链接
题目描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
示例:
- 输入：n = 3
输出：[“((()))”,“(()())”,“(())()”,“()(())”,“()()()”] - 输入：n = 1
输出：[“()”]
提示：
- 1 <= n <= 8
分析:
代码:
class Solution { List<String> ret;// 返回值 StringBuffer path;// 记录搜索路径 int maxLevel, lcnt, rcnt;// max表示最大层数 lcnt表示左括号的数量 rcnt表示右括号的数量 public List<String> generateParenthesis(int n) { ret = new ArrayList<>(); path = new StringBuffer(); if (n == 0) return ret; maxLevel = 2 * n; dfs(1, lcnt, rcnt,n); return ret; } private void dfs(int level, int lcnt, int rcnt,int n) { // 递归出口 if(level > maxLevel) { ret.add(path.toString()); return; } if(lcnt < n) { path.append("("); dfs(level + 1,lcnt+1, rcnt,n); path.deleteCharAt(path.length() - 1);// 回溯 } if(rcnt < n && lcnt > rcnt) { path.append(")"); dfs(level + 1, lcnt, rcnt+1,n); path.deleteCharAt(path.length() - 1);// 回溯 } } }
二.目标和
题目链接
题目描述
给你一个非负整数数组 nums 和一个整数 target。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个表达式：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 "+2-1" 。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。
示例:
- 输入：
nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有5种方法让最终目标和为3。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3 - 输入：
nums = [1], target = 1
输出：1
提示：
- 1 <= nums.length <= 20
- 0 <= nums[i] <= 1000
- 0 <= sum(nums[i]) <= 1000
- -1000 <= target <= 1000
分析:
思路同子集相同,子集中我们的决策策略是选不选当前的数,本题采用+当前数/-当前数
代码:
class Solution { int path, ret, target; public int findTargetSumWays(int[] nums, int _target) { target = _target; dfs(nums,0); return ret; } private void dfs(int[] nums, int pos) { if(pos == nums.length) { if(path == target) ret += 1; return; } // + path += nums[pos]; dfs(nums,pos + 1); path -= nums[pos];//回溯 // - path -= nums[pos]; dfs(nums,pos + 1); path += nums[pos];// 回溯 } }
本题的最优解法其实是动态规划,具体可见我的这篇文章
算法系列–动态规划–背包问题(2)–01背包拓展题目
(有限制条件下的组合问题,且一个数只能选择一次–01背包问题)
3.组合总和
题目链接
题目描述
给你一个无重复元素的整数数组 candidates 和一个目标整数 target，找出 candidates 中可以使数字和为目标数 target 的所有不同组合，并以列表形式返回。你可以按任意顺序返回这些组合。
candidates 中的同一个数字可以无限制重复被选取。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例:
- 输入：
candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。 - 输入:
candidates = [2,3,5], target = 8
输出:[[2,2,2,2],[2,3,3],[3,5]] - 输入:
candidates = [2], target = 1
输出:[]
提示：
- 1 <= candidates.length <= 30
- 2 <= candidates[i] <= 40
- candidates 的所有元素互不相同
- 1 <= target <= 40
分析:
(如果本题是要求组合总和的最多组合数就是一个完全背包问题)
代码:
class Solution { List<List<Integer>> ret; List<Integer> path;// 保存搜索路径 int sum, target;// sum记录搜索路径上的和 public List<List<Integer>> combinationSum(int[] nums, int _target) { ret = new ArrayList<>(); path = new ArrayList<>(); target = _target; dfs(nums,0); return ret; } private void dfs(int[] nums, int pos) { if(sum >= target) {// 递归出口 if(sum == target) { ret.add(new ArrayList<>(path)); } return; } for(int i = pos; i < nums.length; i++) { path.add(nums[i]); sum += nums[i]; dfs(nums,i);// 递归 path.remove(path.size() - 1); sum -= nums[i];// 回溯 } } }
算法系列--递归,回溯,剪枝的综合应用(2)（下）https://developer.aliyun.com/article/1480878?spm=a2c6h.13148508.setting.15.352e4f0en4xYH1
