LeetCode:39. 组合总和
1.思路
嵌套for循环,层数未知,用递归实现。
先对数组排序,方便后面剪枝操作,优化搜索,
确定单层递归的逻辑backtracking(),传入结果集List> res, List path, int[] candidates, int target, int sum, int idx(防止递归调用重复的数字)
最后,对path调用remove(path.size() - 1) 回溯,查找后面复合条件的路径
2.代码实现
1class Solution { 2 public List<List<Integer>> combinationSum(int[] candidates, int target) { 3 List<List<Integer>> res = new ArrayList<>(); // 存储结果的结果集 4 Arrays.sort(candidates); // 对其进行排序,便于剪枝操作(优化搜索过程) 5 backtracking(res, new ArrayList<>(), candidates, target, 0, 0); // 调用递归函数进行回溯搜索 6 return res; 7 } 8 9 public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) { 10 // 如果当前路径的和等于目标值,将路径加入结果集并返回 11 if (sum == target) { 12 res.add(new ArrayList<>(path)); 13 return; 14 } 15 // 遍历数组中的元素 16 for (int i = idx; i < candidates.length; i++) { 17 if (sum + candidates[i] > target) break; // 终止条件:如果当前和大于目标值,剪枝操作 18 path.add(candidates[i]); // 不大于目标和,则将元素加入路径 19 backtracking(res, path, candidates, target, sum + candidates[i], i); // 递归调用下一个元素 20 path.remove(path.size() - 1); // 回溯,移除路径 path 最后一个元素,寻找新的路径 21 } 22 } 23}
3.复杂度分析
时间复杂度:时间消耗取决于for循环层数和递归函数调用次数,则为O(nm)n.
空间复杂度:取决于递归函数调用深度/层数,O(i).
LeetCode:40.组合总和II
1.思路
组合问题,元素有重复,但结果不允许重复,则需要考虑枝干层元素的去重。
设置used[]数组对元素是否重复进行标记,对数组元素进行排序,便于剪枝,优化搜索。
确定递归函数,剪枝操作(sum>target/树层去重),for循环遍历,添加,加和,标记,递归,最后回溯。
2.代码实现
1class Solution { 2 LinkedList<Integer> path = new LinkedList<>(); // 存储当前路径的链表 3 List<List<Integer>> ans = new ArrayList<>(); // 存储所有符合结果的结果集 4 boolean[] used; // 记录元素是否被使用过的数组 5 int sum = 0; // 当前路径元素的和 6 7 public List<List<Integer>> combinationSum2(int[] candidates, int target) { 8 used = new boolean[candidates.length]; // 初始化used[]数组 9 Arrays.fill(used,false); // 全部置为false 10 Arrays.sort(candidates); // 将数组candidates[] 排序,便于剪枝操作,优化搜索 11 backtracking(candidates, target, 0); // 调用递归函数进行递归搜索 12 return ans; 13 } 14 15 private void backtracking(int[] candidates, int target, int startIndex) { 16 // 将符合条件的结果加入到结果集中 17 if (sum == target) { 18 ans.add(new ArrayList(path)); 19 } 20 // 横向遍历所有元素 21 for (int i = startIndex; i < candidates.length; i++) { 22 // 当前路径元素和大于目标target,剪枝操作 23 if (sum + candidates[i] > target) { 24 break; 25 } 26 // 当前节点大于0且遇到重复元素且上一个元素没有用过,则当前元素与后序存在重复,剪枝操作 27 if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) { 28 continue; 29 } 30 // 符合加入路径条件的 31 used[i] = true; // 记录该元素使用过 32 sum += candidates[i]; // sum加上当前元素 33 path.add(candidates[i]); // 将元素值加入路径 34 // 每个节点仅能选择一次,所以从下一位开始 i + 1 35 // 竖向递归选出符合条件的元素 36 backtracking(candidates, target, i + 1); 37 // 回溯——修改used值——和减去最后一个值——路径减去最后一个元素 38 used[i] = false; 39 sum -=candidates[i]; 40 path.removeLast(); 41 } 42 } 43}
3.复杂度分析
时间复杂度:O(2^n)*n.
空间复杂度:O(n).
LeetCode:131.分割回文串
131. 分割回文串 - 力扣(LeetCode)
1.思路
和组合类似的思路,多了个回文子串的判断。
for循环进行横向遍历切割,判断每段字符串为回文子串并输出结果。
2.代码实现
1class Solution { 2 List<List<String>> lists = new ArrayList<>(); // 存放结果的结果集 3 Deque<String> deque = new LinkedList<>(); // 用于存放回文子串的队列 4 5 public List<List<String>> partition(String s) { 6 backtracking(s, 0); // 调用回溯函数进行搜索 7 return lists; // 返回结果集 8 } 9 private void backtracking(String s, int startIndex) { 10 // 遍历到最后位置,startIndex在这里更像是索引 11 if (startIndex >= s.length()) { 12 lists.add(new ArrayList(deque)); // 将结果加入结果集中 13 return; 14 } 15 // 横向遍历字符串 16 for (int i = startIndex; i < s.length(); i++) { 17 // 判断是否是回文字符串 18 if (isPalindrome(s, startIndex, i)) { 19 // 如果是回文串,将其加入到队列中 20 String str = s.substring(startIndex, i + 1); 21 deque.addLast(str); 22 } else { 23 // 不是,则结束本次循环,继续下一次循环 24 continue; 25 } 26 // 递归调用函数,继续搜索下一个回文子串 27 backtracking(s, i + 1); 28 deque.removeLast(); // 回溯 删除队列中最后一个元素,便于加入其他可能的回文子串 29 } 30 } 31 // 判断字符串是否是回文子串 32 private boolean isPalindrome(String s, int startIndex, int end) { 33 // 双指针+for循环遍历 34 for (int i = startIndex, j = end; i < j; i++, j--) { 35 if (s.charAt(i) != s.charAt(j)) { 36 return false; 37 } 38 } 39 return true; 40 } 41}
3.复杂度分析
时间复杂度:O(2^n)*n.
空间复杂度:O(n^2).每次for循环调用一个回溯函数一个回文子串函数.n个元素则调用n^2层的深度