代码随想录Day20

Day20

回溯算法part02

LeetCode 39. 组合总和

题目描述

给你一个 无重复元素 的整数数组 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 。
仅有这两种组合。

题目链接

https://leetcode.cn/problems/combination-sum/

思路

在原有的组合问题上，将startIndex的递归值变为i确保每次元素能够重复使用

解决代码

java">class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);//排序backTracking(candidates, target, 0);return result;}public void backTracking(int[] candidates, int target, int startIndex){if(sum > target){return;}if(sum == target){result.add(new ArrayList<>(path));return;}for(int i = startIndex; i < candidates.length; i++){path.add(candidates[i]);sum += candidates[i];backTracking(candidates, target, i);//递归起始位置为i，确保能重复使用元素sum -= candidates[i];path.removeLast();}}
}

LeetCode 40.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

**注意：**解集不能包含重复的组合。

示例

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

题目链接

https://leetcode.cn/problems/combination-sum-ii/description/

思路

和上一题的关键在于, 确保每层每个元素只遍历一次。涉及到回溯的, 在草稿纸上画图推导过程比较好

解决代码

java">class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();int sum = 0;public List<List<Integer>> combinationSum2(int[] candidates, int target) {        Arrays.sort(candidates);backTracking(candidates, target, 0);return result;}public void backTracking(int[] candidates, int target, int startIndex){ if(sum == target){//找到目标路径result.add(new ArrayList(path));return;}for(int i = startIndex; i < candidates.length; i++){if(sum > target){break;}//确保每层，每个元素只用一次if(i > startIndex && candidates[i] == candidates[i - 1]){continue;}path.add(candidates[i]);sum += candidates[i];backTracking(candidates, target, i + 1);sum -= candidates[i];path.removeLast();}}
}

LeetCode 131.分割回文串

题目描述

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是。返回 s 所有可能的分割方案。

示例

输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]

题目链接

https://leetcode.cn/problems/palindrome-partitioning/description/

思路

这道题可以用隔板法, 每次对字符串放一个隔板(假想)进行一分为二。如果前面的字符串是回文数, 则进行下一层的递归。否则将下一个字符拼接到当前隔板前面的子串后。

递归的终止条件，即隔板位置到字符串最末端。

解决代码

java">class Solution {List<List<String>> result = new ArrayList<>();//存储结果集List<String> path = new ArrayList<>();//存储路径public List<List<String>> partition(String s) {backTrack(s, 0, new StringBuilder());return result;}/*** @param s 待操作字符串* @param startIndex 当前隔板的字符串下标* @param sb 负责拼接字符串*/public void backTrack(String s, int startIndex, StringBuilder sb){if(startIndex == s.length()){//所有隔板已经放完，存入结果集result.add(new ArrayList(path));return;}for(int i = startIndex; i < s.length(); i++){sb.append(s.charAt(i));if(check(sb)){//如果目前已分割的字符串是回文数，执行下一步，否则，隔板放在下一个，拼接下一个字符串到sb中path.add(sb.toString());backTrack(s, i + 1, new StringBuilder());//下一层操作path.removeLast();//回溯}}}//判断是否为回文数public boolean check(StringBuilder str){char[] ch = str.toString().toCharArray();//stringBuilder转换为数组int left = 0, right = ch.length - 1;while(left < right){if(ch[left] != ch[right])return false;left++;right--;}return true;}
}