39.组合总和
文章：7. 组合总和
题目：39. 组合总和
【思路】
需要剪枝：先将数组排好序sort.Ints(arr)，如果arr[i] > target的话，说明后面的值就不需要再去回溯了（因为当前值已经比target大了）。不剪枝的话会超过内存限制噢！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backtracking(candidates,target,0);
return res;
}
public void backtracking(int[] candidates,int target,int start){
if (target == 0){
res.add(new ArrayList<>(path));
return ;
}
for(int i = start;i < candidates.length;i++){
if(candidates[i] > target){
break;
}
path.add(candidates[i]);
backtracking(candidates,target-candidates[i],i);
path.removeLast();
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| func combinationSum(candidates []int, target int) [][]int {
res := make([][]int,0)
path := make([]int,0,len(candidates))
sort.Ints(candidates)
var backtracking func(candidates []int, start, target int)
backtracking = func(candidates []int ,start,target int){
if target == 0{
tmp := make([]int ,len(path))
copy(tmp,path)
res = append(res,tmp)
return
}
for i := start;i<len(candidates);i++{
if candidates[i] > target{
break
}
path = append(path,candidates[i])
backtracking(candidates,i,target-candidates[i])
path = path[:len(path)-1]
}
}
backtracking(candidates,0,target)
return res
}
|
40.组合总和II
文章：8. 组合总和II
题目：40. 组合总和 II
【思路】
这题和上面那题不一样的是数组会存在重复的数字，这时便需要我们设置一个全局变量来记录遍历时数组前一位的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
List<List<Integer>> res = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
int pre = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backtracking(candidates,target,0);
return res;
}
public void backtracking(int[] candidates,int target,int start){
if (target == 0){
res.add(new ArrayList<>(path));
return ;
}
for(int i = start;i < candidates.length;i++){
if(candidates[i] > target){
break;
}
if(pre!= candidates[i]){
path.add(candidates[i]);
backtracking(candidates,target-candidates[i],i+1);
path.removeLast();
pre = candidates[i];
}
}
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| func combinationSum2(candidates []int, target int) [][]int {
res := make([][]int,0)
path := make([]int,0,len(candidates))
pre :=0
sort.Ints(candidates)
var backtracking func(candidates []int, start, target int)
backtracking = func(candidates []int ,start,target int){
if target == 0{
tmp := make([]int ,len(path))
copy(tmp,path)
res = append(res,tmp)
return
}
for i := start;i<len(candidates);i++{
if candidates[i] > target{
break
}
if pre != candidates[i]{
path = append(path,candidates[i])
backtracking(candidates,i+1,target-candidates[i])
path = path[:len(path)-1]
pre = candidates[i]
}
}
}
backtracking(candidates,0,target)
return res
}
|
131.分割回文串
文章：9. 分割回文串
题目：131. 分割回文串
【思路】
分割回文串问题，叶子节点即为我们需要的结果，添加进res集合
递归函数参数
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。（这两个参数可以当到函数参数里。）
本题递归函数还需要startIndex，因为切割过的地方不能重复切割，和组合问题也是保持一致的。
递归函数终止条件
切割线切到了字符串后面，说明找到了一种切割方法，此时就是本层递归的终止条件。
单层搜索的逻辑
在for循环中，我们定义了起始位置startIndex，那么[startIndex,i]就是要截取的子串。首先判断这个子串是不是回文，如果是回文，就加入res，path用来记录切割过的回文子串。
判断回文子串
可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串。
Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
List<List<String>>res = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
backtracking(s,0);
return res;
}
public void backtracking(String s,int startIndex){
if(startIndex >= s.length()){
res.add(new ArrayList<>(path));
return ;
}
for(int i = startIndex ; i < s.length();i++ ){
if(isPalindrome(s,startIndex,i)){
String str = s.substring(startIndex,i+1);
path.add(str);
}else{
continue;
}
backtracking(s,i+1);
path.removeLast();
}
}
public boolean isPalindrome(String s ,int startIndex,int end){
for (int i = startIndex,j = end;i<j;i++,j--){
if(s.charAt(i)!= s.charAt(j)){
return false;
}
}
return true;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
| var(
path []string
res [][]string
)
func partition(s string) [][]string {
path,res = make([]string,0),make([][]string,0)
backtracking(s,0)
return res
}
func backtracking(s string,start int){
if start == len(s){
tmp := make([]string,len(path))
copy(tmp,path)
res = append(res,tmp)
return
}
for i:= start;i<len(s);i++{
str := s[start:i+1]
if isPalindrome(str){
path = append(path,str)
backtracking(s,i+1)
path = path[:len(path)-1]
}
}
}
func isPalindrome(s string) bool {
for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
if s[i] != s[j] {
return false
}
}
return true
}
|
【算法总结】
- 组合总和：需要使用回溯来对给出的数字进行分割组合，需要用剪枝节省时间，不然会超时
- 组合总和II：需要使用回溯，和以上的题思路相似，但是需要注意本题给的数据会出现重复的值，因此我们要使用一个全局变量来标记。
- 分割回文串：回溯+双指针法，需要注意边界条件。
