算法笔记|Day20回溯算法II

☆☆☆☆☆leetcode 39. 组合总和

题目链接：leetcode 39. 组合总和

题目分析

本题采用回溯算法，组合没有数量要求，且元素可无限重复选取，故每次遍历都可以从第一个元素开始。

代码

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path=new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {backtrcking(candidates,target,0,0);return res;}public void backtrcking(int candidates[],int target,int sum,int start){if(sum>target)return;if(sum==target){res.add(new ArrayList(path));return;}for(int i=start;i<candidates.length;i++){sum+=candidates[i];path.add(candidates[i]);backtrcking(candidates,target,sum,i);sum-=candidates[i];path.removeLast();}}
}

☆☆☆☆☆leetcode 40.组合总和II

题目链接：leetcode 40.组合总和II

题目分析

本题集合（数组candidates）有重复元素，但不能有重复的组合，涉及到去重的逻辑，采用了used数组，若该元素在本轮回溯遍历（树层）中用到过赋值为1，后续不再使用，回溯时恢复为0；但在递归遍历（树枝）中用到过，还可以继续使用。

代码

class Solution {List<List<Integer>> res=new ArrayList<>();List<Integer> path=new LinkedList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);int used[]=new int[candidates.length];backtracking(candidates,target,0,0,used);return res;}public void backtracking(int candidates[],int target,int sum,int start,int used[]){if(sum>target)return;if(sum==target){res.add(new ArrayList(path));return;}for(int i=start;i<candidates.length;i++){if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==0)continue;sum+=candidates[i];path.add(candidates[i]);used[i]=1;backtracking(candidates,target,sum,i+1,used);sum-=candidates[i];path.removeLast();used[i]=0;}}
}

☆☆☆☆☆leetcode 131.分割回文串

题目链接：leetcode 131.分割回文串

题目分析

切割问题可以仿照组合问题利用回溯，从前往后搜索，如果发现回文，进入backtracking，起始位置后移一位，循环结束照例移除str的末位。

代码

class Solution {List<List<String>> res=new ArrayList<>();List<String> str=new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s,0,new StringBuilder());return res;}public void backtracking(String s,int start,StringBuilder sb){if(start==s.length()){res.add(new ArrayList(str));return;}for(int i=start;i<s.length();i++){sb.append(s.charAt(i));if(check(sb)){str.add(sb.toString());backtracking(s,i+1,new StringBuilder());str.removeLast();}}}public boolean check(StringBuilder sb){for(int i=0;i<sb.length()/2;i++){if(sb.charAt(i)!=sb.charAt(sb.length()-1-i))return false;}return true;}
}

提示：回文串是向前和向后读都相同的字符串，可以考虑使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了；也可以直接判断前一半元素和对称位置的元素是否相等。