代码随想录Day23—回溯2

目录

39 组合总合

---

39 组合总合

注意注释掉的，如果把sum放外面做加减的话，之后回溯的时候需要，减去那个值。

class Solution {List<List<Integer>> result = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);fun(result, new ArrayList<>(), target, candidates, 0, 0);return result;}public void fun(List<List<Integer>> result, List<Integer> path, int target, int[] candidates, int sum, int index) {if (sum == target) {result.add(new ArrayList<>(path));return;}for (int i = index; i < candidates.length; i++) {if (sum + candidates[i] > target)break;path.add(candidates[i]);// fun(result,path,target,candidates,sum+candidates[i],i);sum += +candidates[i];fun(result, path, target, candidates, sum, i);sum -= +candidates[i];path.remove(path.size() - 1);}}
}

40 组合总和II

去重。

和39思路差不多，注意需要跳过重复元素，因为一个数组中可能会有两个一样的数字。

class Solution {public List<List<Integer>> combinationSum2(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(candidates);fun(candidates, target, result, new ArrayList<>(), 0, 0);return result;}public void fun(int[] candidates, int target, List<List<Integer>> result, List<Integer> path, int sum, int index) {if (sum == target) {result.add(new ArrayList<>(path));return;}for (int i = index; i < candidates.length && sum + candidates[i] <= target; i++) {// 跳过同一树层使用过的元素if (i > index && candidates[i] == candidates[i - 1])continue;path.add(candidates[i]);fun(candidates, target, result, path, sum + candidates[i], i + 1);path.remove(path.size() - 1);}}
}

131 分割回文串

切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段.....。

注意细节，比如需要toString()等。

有点生疏，字符串语法。

class Solution {List<List<String>> res = new ArrayList<>();List<String> cur = new ArrayList<>();public List<List<String>> partition(String s) {fun(s,0,new StringBuffer());return res;}public void fun(String s, int index, StringBuffer s1) {if (index == s.length()) {res.add(new ArrayList<>(cur));return;}for(int i=index;i<s.length();i++){s1.append(s.charAt(i));if(check(s1)){cur.add(s1.toString());fun(s,i+1,new StringBuffer());cur.remove(cur.size()-1);}}}public boolean check(StringBuffer s1) {for (int i = 0, j = s1.length() - 1; i < j; i++, j--) {if (s1.charAt(i) != s1.charAt(j))return false;}return true;}
}