leetcode46 全排列
使用回溯思想
for循环遍历每次选取的数
递归遍历下一次选取的数
选取完回溯 将暂时保存的path删除尾部 将used重置为0
class Solution {
List<List<Integer>> res;
List<Integer> path;
public List<List<Integer>> permute(int[] nums) {
res = new ArrayList<>();
path = new ArrayList<>();
backtracking(nums,new int[nums.length]);
return res;
}
public void backtracking(int[] nums,int[] used){
if(path.size() == nums.length){
res.add(new ArrayList<>(path));
return;
}
for(int i=0;i<nums.length;i++){
if(used[i] ==1) continue;
path.add(nums[i]);
used[i]=1;
backtracking(nums,used);
path.removeLast();
used[i]=0;
}
}
}
leetcode 78. 子集
考虑添加结果的时间点 不是在递归出口, 而是在每次更新path的时候,每次递归会使得横向遍历的结果缩小变成i+1,回溯阶段删除path的末尾
class Solution {
List<List<Integer>> res;
List<Integer> path ;
public List<List<Integer>> subsets(int[] nums) {
res = new ArrayList<>();
path = new ArrayList<>();
res.add(path);
backtracking(nums,0);
return res;
}
public void backtracking(int[] nums,int startIndex){
if(startIndex >=nums.length){
return;
}
for(int i = startIndex;i<nums.length;i++){
path.add(nums[i]);
res.add(new ArrayList(path));
backtracking(nums,i+1);
path.removeLast();
}
}
}
leetcode 17. 电话号码的字母组合
横向for循环每个按钮里的值
递归下一层则是换一个按钮
每次都是从0开始,digit的长度为几就递归深度为几
class Solution {
List<String> res;
StringBuilder sb;
public List<String> letterCombinations(String digits) {
String[] strs = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
res = new ArrayList<>();
if(digits.length()<=0) return res;
sb = new StringBuilder();
backTracking(digits,0,strs);
return res;
}
public void backTracking(String digits,int index,String[] strs){
if(index >= digits.length()){
res.add(sb.toString());
return;
}
String temp = strs[digits.charAt(index)-'0'];
for(int i =0;i<temp.length();i++){
sb.append(temp.charAt(i));
backTracking(digits,index+1,strs);
sb.deleteCharAt(sb.length()-1);
}
}
}
leetcode 39. 组合总和
递归出口为结果等于target,如果大于target也退出递归 因为 输入数字串是从小到大排列
第一层递归要从当前值取起,但是每一层for循环会使i+1
回溯 删除结果末尾的值
class Solution {
List<List<Integer>> res;
List<Integer> path;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new ArrayList<>();
path = new ArrayList<>();
backTracking(candidates,target,0,0);
return res;
}
public void backTracking(int[] candidates,int target,int total,int index){
if(total>target){
return;
}
if(total== target){
res.add(new ArrayList<>(path));
return;
}
for(int i =index;i<candidates.length;i++){
path.add(candidates[i]);
backTracking(candidates,target,total+candidates[i],i);
path.removeLast();
}
}
}
leetcode 22. 括号生成
待取值数组为(),每一次向下递归不会改变,for循环01 0为( 1 为),递归出口 l》n||r》n||r>l则直接退出不保存结果
lr && ln 则保存结果并退出
class Solution {
List<String> res;
StringBuilder sb = new StringBuilder();
public List<String> generateParenthesis(int n) {
res = new ArrayList<>();
backTracking(0,0,n);
return res;
}
public void backTracking(int l,int r,int n){
if(r>n || l>n || r>l){
return;
}
if(l==r && l==n){
res.add(sb.toString());
}
for(int i =0;i<2;i++){
if(i==0){
sb.append("(");
backTracking(l+1,r,n);
}
else if(i==1)
{
sb.append(")");
backTracking(l,r+1,n);
}
sb.deleteCharAt(sb.length()-1);
}
}
}