回溯算法-Java【力扣】【算法学习day.14】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

---

什么是回溯算法

        回溯搜索法是一种搜索方式，它通过不断尝试各种可能的选择，当发现当前选择不满足条件时，就回溯到上一个状态，重新进行选择，直到找到满足条件的解或者遍历完所有可能的情况。例如在解决迷宫问题时，可以使用回溯搜索法，从一个起始位置开始尝试不同的方向前进，如果遇到死路就回溯到上一个位置，重新选择其他方向。

---

习题

1.组合

题目链接:77. 组合 - 力扣（LeetCode）

题面:

基本分析:抽象成树的结构进行递归

代码:

class Solution {int len;public List<List<Integer>> combine(int n, int k) {List<List<Integer>> ans = new ArrayList<>();Stack<Integer> stack = new Stack<>();len = k;recursion(1,n,ans,stack);return ans;}public void recursion(int start,int end,List<List<Integer>> ans,Stack<Integer> stack){if(stack.size()==len){ans.add(new ArrayList<>(stack));return;}for(int i = start;i<=end - (len - stack.size()) + 1;i++){stack.push(i);recursion(i+1,end,ans,stack);stack.pop();}}
}

---

2.组合总和III

题目链接:216. 组合总和 III - 力扣（LeetCode）

题面:

基本分析:和上一题类似，只不过多一个判断相加之和 

代码:

class Solution {int len;int target;public List<List<Integer>> combinationSum3(int k, int n) {List<List<Integer>> ans = new ArrayList<>();len = k;target = n;Stack<Integer> stack = new Stack<>();recursion(1,9,stack,ans,0);return ans;}public void recursion(int l,int r,Stack<Integer> stack,List<List<Integer>> ans,int sum){if(sum>target)return;if(stack.size()>len)return;if(sum==target&&stack.size()==len)ans.add(new ArrayList<>(stack));for(int i = l;i<=r-(len-stack.size())+1;i++){stack.push(i);recursion(i+1,r,stack,ans,sum+i);stack.pop();}}
}

3.电话号码的字母组合

题目链接:17. 电话号码的字母组合 - 力扣（LeetCode）

题面:

基本分析:暴力递归

代码:

class Solution {char[][] arr = {{'d'},{'a'},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};int count = -1;int len;public List<String> letterCombinations(String digits) {List<String> list = new ArrayList<>();if(digits.equals(""))return list;              char[] brr = digits.toCharArray();int n = brr.length;len = n;char[] crr = new char[n];recursion(0,brr,crr,list);return list;}public void recursion(int u,char[] brr,char[] crr,List<String> list){if(u==len){list.add(new String(crr));return;}char c = brr[u];char[] drr = arr[c-'0'];int m = drr.length;for(int i = 0;i<m;i++){crr[++count]=drr[i];recursion(u+1,brr,crr,list);count--;}}
}

---

4.组合总和

题目链接:39. 组合总和 - 力扣（LeetCode）

题面:

基本分析:注意剪枝来去重

代码:

class Solution {int[] arr;int len;int t;public List<List<Integer>> combinationSum(int[] candidates, int target) {arr = candidates;List<List<Integer>> list = new ArrayList<>();List<Integer> stack = new Stack<>();len = candidates.length;t = target;Arrays.sort(arr);recursion(list,stack,0,0);return list;}public void recursion(List<List<Integer>> list,List<Integer> stack,int sum,int l){if(sum==t){list.add(new ArrayList<>(stack));return;}for(int i = l;i<len;i++){if(sum+arr[i]>t)return;stack.add(arr[i]);recursion(list,stack,sum+arr[i],i);stack.remove(stack.size()-1);}}
}

---

5.组合总和II

题目链接:40. 组合总和 II - 力扣（LeetCode）

题面:

基本分析:注意重复元素导致的重复,用set是一种解决办法但是会超时

代码:

class Solution {int t;int[] arr;int n;public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);arr = candidates;Set<List<Integer>> list = new HashSet<>();List<Integer> stack = new ArrayList<>();n = arr.length;t = target;recursion(list,stack,0,0);return new ArrayList<>(list);}public void recursion(Set<List<Integer>> list,List<Integer> stack,int sum,int l){if(sum==t){list.add(new ArrayList<>(stack));return;}for(int i =l;i<n;i++){if(sum+arr[i]>t)return;if (i > l && arr[i] == arr[i - 1]) {continue;}stack.add(arr[i]);recursion(list,stack,sum+arr[i],i+1);stack.remove(stack.size()-1);}}
}

---

后言

上面是回溯算法的基本概念和部分习题，下一篇会讲解回溯算法的其他相关力扣习题，希望有所帮助，一同进步，共勉！