回溯算法-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);
        }
    }
}