算法之回溯专题

前言

回溯是我的薄弱点，所以写点杀卡尔的题目

首先来看杀卡写的模板吧，有一说一还挺有用

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

77. 组合 - 力扣（LeetCode）

这个还是简单的，但我还是没剪枝！

class Solution {
    //组合问题呢，就得有starindex了，因为不能重复啊
    ArrayList<Integer>path=new ArrayList<>();
    List<List<Integer>>res=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        back(n, k, 1);
        return res;
    }
    void back(int n,int k,int starIndex)
    {
        if(path.size()==k)
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=starIndex;i<=n;i++)
        {
            path.add(i);
            back(n, k, i+1);
            path.remove(path.size()-1);
        }
    }
}

剪枝：

class Solution {
    //组合问题呢，就得有starindex了，因为不能重复啊
    ArrayList<Integer>path=new ArrayList<>();
    List<List<Integer>>res=new ArrayList<>();
    public List<List<Integer>> combine(int n, int k) {
        back(n, k, 1);
        return res;
    }
    void back(int n,int k,int starIndex)
    {
        if(path.size()==k)
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=starIndex;i<=n-(k-path.size())+1;i++)//就是这里变了，
        {
            path.add(i);
            back(n, k, i+1);
            path.remove(path.size()-1);
        }
    }
}

17. 电话号码的字母组合 - 力扣（LeetCode）

我一开始的误区是什么

我一开始写成了

void back(String digits,String[]numString,int starIndex,int num)
    {
        if(num==digits.length())
        {
            list.add(temp.toString());
            return;
        }
        for(int i=starIndex;i<numString[i].length();i++)
        {
            temp.append(numString[num].charAt(i));
            back(digits, numString, , num);
        }
    }

我想的是,”ab”,”cd”，然后每个里面也需要去重，

但是其实是不需要的，因为你ac,ae,agxxxxx都是算的，所以不需要starindex

正解：

class Solution { 
    List<String> list = new ArrayList<>();
     StringBuilder temp = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return list;
        }
         String[] numString = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};//建立一个一一对应关系
         back(digits, numString, 0);
         return list;
    }
    //一个组合问题，这边不用starIndx，因为你ad,ag,aj都算的啊
    void back(String digits,String[]numString,int num)
    {
        if(num==digits.length())
        {
            list.add(temp.toString());
            return;
        }
        String str=numString[digits.charAt(num)-'0'];

        for(int i=0;i<str.length();i++)
        {
            temp.append(str.charAt(i));
            back(digits, numString, num+1);
            temp.deleteCharAt(temp.length()-1);
        }
    }

}

39. 组合总和 - 力扣（LeetCode）

自己写居然一遍过，太屌了

class Solution {
    ArrayList<Integer>path=new ArrayList<>();
    List<List<Integer>>res=new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        back(candidates, target, 0,0);
        return res;

    }
    //有一说一这个里面隐藏了剪枝问题,写到了再说
    //然后可以重复选取，那么就可以从0开始
    void back(int []candidates,int target,int sum,int startIndex)//sum是当前和
    {
        //返回条件
        if(sum>target)
        {
            
            return;
        }
        else if(sum==target)
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<candidates.length;i++)
        {
            sum+=candidates[i];
            path.add(candidates[i]);
            back(candidates, target, sum,i);
            sum-=candidates[i];
            path.remove(path.size()-1);
        }
    }
}

但我知道是可以剪枝的，如何剪枝呢

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates); // 先进行排序
        backtracking(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        // 找到了数字和为 target 的组合
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = idx; i < candidates.length; i++) {
            // 如果 sum + candidates[i] > target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); // 回溯，移除路径 path 最后一个元素
        }
    }
}

如果大于了就直接终止遍历，注意这样得先排序

40. 组合总和 II - 力扣（LeetCode）

这个去重已经是套路了

class Solution {
    ArrayList<Integer>path=new ArrayList<>();
    List<List<Integer>>res=new ArrayList<>();
    int sum=0;
    boolean[]isvisited;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        isvisited=new boolean[candidates.length];
        back(candidates, target, 0);
        return res;
    }

    void back(int []candidates,int target,int startIndex)
    {
        if(sum==target)
        {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i=startIndex;i<candidates.length;i++)
        {
            if(sum+candidates[i]>target)
            {
                break;
            }
            if(i>0&&candidates[i]==candidates[i-1]&&!isvisited[i-1])
            {
                continue;
            }
            isvisited[i]=true;
            sum+=candidates[i];
            path.add(candidates[i]);
            back(candidates, target, i+1);
            isvisited[i]=false;
            sum-=candidates[i];
            path.remove(path.size()-1);
        }
    }
}

131. 分割回文串 - 力扣（LeetCode）

我一开始的误区是，没有看清题，没看到是要分割，还以为是找到所有的回文字符串

然后分割的具体，是startIndex作为第一刀，i作为第二刀，这个思路要会

class Solution {
     List<List<String>> lists = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();
    public List<List<String>> partition(String s) {
        back(s, 0);
        return lists;
    }

    private 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;
    }

    void back(String s ,int startIndex)//以starx开始分割，i作为分割的右边界
    {
        if(startIndex>=s.length())
        {
            lists.add(new ArrayList<>(deque));
            return;
        }
        for(int i=startIndex;i<s.length();i++)
        {
            if(isPalindrome(s, startIndex, i))
            {
                String str=s.substring(startIndex,i+1);
                deque.add(str);                
            }else
            {
                continue;
            }
            back(s, i+1);
            deque.removeLast();
        }
    }
}

78. 子集 - 力扣（LeetCode）

这题比较简单，注意了，为什么add刀res的操作不在if里面呢

因为我们本来就是要无条件的把所有的情况全加进去，所以直接add就行了

class Solution {
    //子集问题，这个就比较简单了，只要记得starIndex就行了
    ArrayList<Integer>path=new ArrayList<>();
    List<List<Integer>>res=new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        back(nums, 0);
        return res;
    }
    void back(int []nums,int starIndex)
    {   
        res.add(new ArrayList<>(path));
        if(starIndex>=nums.length)
        {
            return;
        }
        for(int i=starIndex;i<nums.length;i++)
        {
            path.add(nums[i]);
            back(nums, i+1);
            path.remove(path.size()-1);
        }
    }
}

90. 子集 II - 力扣（LeetCode）

也是去重问题，和组合总和II一个套路

class Solution {
     ArrayList<Integer>path=new ArrayList<>();
    List<List<Integer>>res=new ArrayList<>();
    boolean []isused;
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        isused=new boolean[nums.length];
        Arrays.sort(nums);
        back(nums, 0);
        return res;

    }
    
    void back(int []nums,int starIndex)
    {   
        res.add(new ArrayList<>(path));//但是这里也是一样的，子集问题存所有的情况，所以先add就行了
        if(starIndex>=nums.length)
        {
            return;
        }
        for(int i=starIndex;i<nums.length;i++)
        {   
            if(i>0&&nums[i]==nums[i-1]&&!isused[i-1])
            {
                continue;
            }
            path.add(nums[i]);
            isused[i]=true;
            back(nums, i+1);
            path.remove(path.size()-1);
            isused[i]=false;
        }
    }
}

491. 递增子序列 - 力扣（LeetCode）

我一开始写的：

if(startIndex>=nums.length)
        {
            res.add(new ArrayList<>(path));
    return;
        }

这样对吗？这样不对啊，因为你是要存入[4,7],[4,7,7],[4,7,7,8],所以你不需要返回，而是路径上的所有节点，都得被存入res里

所以按道理来说不写终止条件是可以的，就和子集问题一样

正确的情况应该是：

if(path.size()>1)
        {
            res.add(path);
        }

然后这里还有一个hs不remove的为什么

class Solution {
    //很明显要starIndex
    ArrayList<Integer>path=new ArrayList<>();
    List<List<Integer>> res=new ArrayList<>();
    public List<List<Integer>> findSubsequences(int[] nums) {
        back(nums, 0);
        return res;
    }

    void back(int []nums,int startIndex)
    {
        if(path.size()>1)
        {
            res.add(new ArrayList<>(path));
        }
        HashSet<Integer>hs=new HashSet<>();
        for(int i=startIndex;i<nums.length;i++)
        {
            if(!path.isEmpty()&&path.get(path.size()-1)>nums[i]||hs.contains(nums[i]))
            {
                continue;
            }
            hs.add(nums[i]);
            path.add(nums[i]);
            back(nums, i+1);
            path.remove(path.size()-1);//为什么hs这里没有remove呢，因为你hs并不是全局变量，而是只记录每一层，相当于每一层一个hs
        }
    }
}

46. 全排列 - 力扣（LeetCode）

排列吗，那就不用starIndex了，每次从头开始，但是你得跳过已经在path里面的，所以需要used

鉴定为易啊

class Solution {
    List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合
    LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果
    boolean[] used;
    public List<List<Integer>> permute(int[] nums) {
        used=new boolean[nums.length];
        back(nums);
        return result;
    }

    void back(int []nums)
    {
        if(path.size()==nums.length)
        {
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(used[i])
            {
                continue;
            }
            used[i]=true;
            path.add(nums[i]);
            back(nums);
            used[i]=false;
            path.remove(path.size()-1);
        }
    }
}

47. 全排列 II - 力扣（LeetCode）

怎么去重和子集问题是一个套路

class Solution {
      //存放结果
    List<List<Integer>> result = new ArrayList<>();
    //暂存结果
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean []used=new boolean[nums.length];
        Arrays.sort(nums);
        back(nums, used);
        return result;
    }

    void back(int[]nums,boolean[]used)
    {
        if(path.size()==nums.length)
        {
            result.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<nums.length;i++)
        {
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1])
            {
                continue;
            }
            //这里还得判断自己用没用过
            if(used[i]==false)
            {
                used[i]=true;
                path.add(nums[i]);
                back(nums, used);
                path.remove(path.size()-1);
                used[i]=false;
            }
        }
    }
}

51. N 皇后 - 力扣（LeetCode）

有一说一难点不在思考本身，而是在处理二维数组和check

class Solution {
    //思路：首先棋盘是二维数组，但是输出形式是每个棋盘是一维数组，所以需要二维转一维String数组的函数
    //然后需要检查斜线，所以还需要check函数
    //然后back，应该是一行一行放
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] c : board) {
            Arrays.fill(c, '.');
        }
        back(n, 0, board);
        return res;
    }

    void back(int n,int row,char[][]board)
    {
        if(row==n)
        {
            res.add(Array2List(board));
            return;
        }
        for(int i=0;i<n;i++)
        {
            if(isValid(row, i, n, board))
            {
                board[row][i]='Q';
                back(n, row+1, board);
                board[row][i]='.';//回溯
            }
        }
    }
    
    
    public boolean isValid(int row,int col,int n,char[][]board)
    {
        for(int i=0;i<row;i++)
        {
            if(board[i][col]=='Q')
                return false;
        }

        for(int j=0;j<row;j++)
        {
            if(board[row][j]=='Q')
            return false;
        }

        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
        {
            if(board[i][j]=='Q')
            return false;
        }

        for(int i=row-1,j=col+1;i>=0&&j<=n-1;i--,j++)
        {
            if(board[i][j]=='Q')
            return false;
        }
        return true;
    }

    public List Array2List(char[][]board)
    {
        List<String> list=new ArrayList<>();
        for(char[]c:board)
        {
            list.add(String.copyValueOf(c));
        }
        return list;
    }
}