回溯算法总结

下面的八个关于排列组合的题目套路都是一样的。都是排列组合问题，只是形式不一样

无论形式怎么变化，其本质就是穷举所有解，而这些解呈现树形结构，所以合理使用回溯算法框架，稍改代码框架即可把这些问题一网打尽。

算法大致模板：

   List<List<Integer>> res = new LinkedList<>();  //返回的值
   LinkedList<Integer> track = new LinkedList<>(); //记录的路径
    public static List<List<Integer>> permute(int[] nums) {
        backtrack(nums, track); //这里面的参数根据不同题目做出不同改变
        return res;
    }
    static void backtrack(int[] nums, LinkedList<Integer> track) {
        // 这里根据不同题目做出不同改变
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if () {
                continue;
            }
              if () {
                continue;
            }
            // 做选择
            track.add(nums[i]);
            // 进入下一层决策树
            backtrack(nums, track);
            // 取消选择
            track.removeLast();
        }
    }

核心：选择=》递归再选择=》取消选择来进行回溯

46. 全排列

题目描述：

思路：经典全排列 解法：递归+回溯

代码：

import java.util.LinkedList;
import java.util.List;

class Solution {

  static   List<List<Integer>> res = new LinkedList<>();

    /* 主函数，输入一组不重复的数字，返回它们的全排列 */
    public static List<List<Integer>> permute(int[] nums) {
        // 记录「路径」
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    static void backtrack(int[] nums, LinkedList<Integer> track) {
        // 触发结束条件
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (track.contains(nums[i])) {
                continue;
            }
            // 做选择
            track.add(nums[i]);
            // 进入下一层决策树
            backtrack(nums, track);
            // 取消选择
            track.removeLast();
        }
    }

    public static void main(String[] args) {
        int[] ints = {1,2，,3};
        List<List<Integer>> permute = permute(ints);
        System.out.println(permute);
    }
}

78. 子集

题目描述：

思路：回溯 通过保证元素之间的相对顺序不变来防止出现重复的子集。

解法：

import java.util.ArrayList;
import java.util.List;

class Solution {
     static List<List<Integer>> res;
    static List<Integer> list = new ArrayList<>();
    public static List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        backTracing(nums, 0);
        return res;
    }
    public static void backTracing(int[] nums, int start){
        // 每更新一次list  都加入结果集  首次进来加的是空集
        res.add(new ArrayList<>(list)); //res.add(new ArrayList<>(list)); 不能写成这样 因为会导致结果不正确（res里面所有的list都变成相同的了）
        // 到数组末尾结束当前递归
        if(start == nums.length){
            return;
        }
        for(int i = start; i < nums.length; i++){
            // 将当前数加入list
            list.add(nums[i]);
            // 递归 不能重复使用当前数 因此下一轮从i+1开始
            backTracing(nums, i+1);
            // 回溯 回退刚刚加的数
            list.remove(list.size()-1);
        }
    }

    public static void main(String[] args) {
        int[] ints = {1, 2，3};
        List<List<Integer>> subsets = subsets(ints);
        System.out.println(subsets);
    }
}

90. 子集 II

题目描述：

思路：

因为不能重复所以要采用剪枝

就以 nums = [1,2,2] 为例，为了区别两个 2 是不同元素，后面我们写作 nums = [1,2,2']。

按照之前的思路画出子集的树形结构，显然，两条值相同的相邻树枝会产生重复：

[ 
    [],
    [1],[2],[2'],
    [1,2],[1,2'],[2,2'],
    [1,2,2']
]

所以我们需要进行剪枝，如果一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历：

体现在代码上，需要先进行排序，让相同的元素靠在一起，如果发现 nums[i] == nums[i-1]，则跳过

[

编码：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {
   static List<List<Integer>> res = new LinkedList<>();
   static LinkedList<Integer> track = new LinkedList<>();

   static public List<List<Integer>> subsetsWithDup(int[] nums) {
        // 先排序，让相同的元素靠在一起
        Arrays.sort(nums);
        backtrack(nums, 0);
        return res;
    }

  static   void backtrack(int[] nums, int start) {
        // 前序位置，每个节点的值都是一个子集
        res.add(new LinkedList<>(track));

        for (int i = start; i < nums.length; i++) {
            // 剪枝逻辑，值相同的相邻树枝，只遍历第一条
            if (i > start && nums[i] == nums[i - 1]) { //很巧妙这个地方
                continue;
            }
            track.addLast(nums[i]);
            backtrack(nums, i + 1);
            track.removeLast();
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = subsetsWithDup(new int[]{1, 2, 2});
        for (List<Integer> list : lists) {
            System.out.println(list);
        }
    }
}

77. 组合

题目描述：

思路：

画个图出来感觉就是回溯，既然是回溯当然先往 选择-》再选择-》取消选择的模板上套啦

代码：

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Solution {
    static  List<List<Integer>> res = new LinkedList<>();
    // 记录回溯算法的递归路径
    static LinkedList<Integer> track = new LinkedList<>();

    // 主函数
    public static List<List<Integer>> combine(int n, int k) {
        backtrack(1, n, k);
        return res;
    }

    static void backtrack(int start, int n, int k) {

        if(k==track.size()) {
            res.add(new LinkedList<>(track));
            return;
        }for(int i=start;i<=n;i++) {
            //选择
            track.add(i);
            //进入下一次决策树
            backtrack(i+1, n, k);
            //取消选择
            track.removeLast();
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> combine = combine(3, 2);
        System.out.println(combine);

    }
}

39. 组合总和（ac）

题目描述：

思路：

给人的第一想法就是递归+回溯 于是乎套用选择=》再选择=》取消选择的模板一套 具体情况具体分析 写出如下代码：

import java.util.LinkedList;
import java.util.List;
class Solution {
    static List<List<Integer>> res=new LinkedList<List<Integer>>();
    //记录路径
    static LinkedList<Integer> track=new LinkedList<Integer>();
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtrack(candidates, 0, target, 0);
        return res;
    }
    private static void backtrack(int[] candidates, int start, int target, int sum) {
        if(sum==target) {
            res.add(new LinkedList<Integer>(track));
        }
        if(sum>target) {
            return ;
        }
        for(int i=start;i<candidates.length;i++) {
            //选择
            track.add(candidates[i]);
            //进入下一次决策树
            backtrack(candidates, i, target, sum+candidates[i]);
            //取消选择
            track.removeLast();
        }

    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        List<List<Integer>> combinationSum = combinationSum(new int [] {2,3,5}, 5);
        for (List<Integer> list : combinationSum) {
            System.out.println(list);
        }

    }
    }

40. 组合总和 II（ac）

题目描述：

思路：

第一感觉就是回溯+递归，套用模板，画个大概图发现需要需要进行剪枝，于是乎编写代码：

class Solution {
    List<List<Integer>> res=new LinkedList<List<Integer>>();
    //记录路径
    LinkedList<Integer> track=new LinkedList<Integer>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); //一定要排序 不然结果会错误
        backtrack(candidates, 0, target, 0);
        return res;
    }
    private  void backtrack(int[] candidates, int start, int target, int sum) {
        if(sum==target) {
            res.add(new LinkedList<Integer>(track));
        }
        if(sum>target) {
            return ;
        }
        for(int i=start;i<candidates.length;i++) {
            //判断进行 剪枝操作
            if(i>start&&candidates[i]==candidates[i-1]){
                continue;
            }
            //选择
            track.add(candidates[i]);
            //进入下一次决策树
            backtrack(candidates, i+1, target, sum+candidates[i]);
            //取消选择
            track.removeLast();
        }

    }
}

216. 组合总和 III（ac）

题目描述：

思路：回溯+递归 第一感觉还是那套模板

于是乎，改改模板得到以下代码

import java.util.LinkedList;
import java.util.List;
class Solution {
  static   List<List<Integer>> res = new LinkedList<>();
    //记录路径
   static LinkedList<Integer> track = new LinkedList<Integer>();
  static   public List<List<Integer>> combinationSum3(int k, int n) {
        backtrack(k,n,1,0,0);

        return res;
    }
  static   private void backtrack(int k, int n,int start,int sum,int count) {

        if(sum>n) {
            return;
        }

        // TODO Auto-generated method stub
        if(k==count&&sum==n) {
            res.add(new LinkedList<>(track));
        }
        for(int i=start;i<6;i++) {
            //选择
            track.add(i);
            count++;
            //进入下一次决策树
            backtrack(k,n,i+1,sum+i,count);
            //取消选择
            count--;
            track.removeLast();
        }
    }
    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum3(3, 7);
        System.out.println(lists);
    }
}

47. 全排列 II

题目描述：

说实话这题想到了大概怎么写，但是没想到怎么处理从0开始会产生复选的问题，所以看了下答案，是用一个布尔型的used数组作为标记。

题解：

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();
    boolean[] used;

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);//排序 这步很重要 不排序的会错误 剪枝的前提是排序
        used=new boolean [nums.length];
       backtrack(nums);
        return res;
    }

    private void backtrack(int[] nums) {
        if(track.size()==nums.length){
            res.add(new LinkedList<>(track));
        }
        for (int i=0;i<nums.length;i++){
            if (used[i]){
                continue;
            }
            //剪枝
            if (i>0&&nums[i]==nums[i-1]&&!used[i-1]){  //剪枝的used[i-1]也很重要
                continue;
            }
            //选择
            used[i]=true;
            track.add(nums[i]);
            //进入下一次决策树
            backtrack(nums);
            //取消选择
            used[i]=false;
            track.removeLast();
        }
    }


}

扩展一题蓝桥杯的全排列

蓝桥杯纸牌三角形（蛮难的）

题目描述：

思路：全排列

代码：

public class Solution {
    static int count = 0;

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
        dfs(arr, 0);
        System.out.println(count / 6);
    }

    // 全排列
    public static void dfs(int[] arr, int index) {
        if (index == arr.length) {
            // 已经够成一个了
            int col = arr[0] + arr[1] + arr[3] + arr[5];
            int row = arr[5] + arr[6] + arr[7] + arr[8];
            int xie = arr[0] + arr[2] + arr[4] + arr[8];
            if (col > 0 && col == row && row == xie) {
                count++;
            }
            return;
        }
        for (int i = index; i < arr.length; i++) {
            swap(arr, index, i);
            dfs(arr, index + 1);
            swap(arr, index, i);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

22. 括号生成

题目描述：

看这题想到了要用什么算法写，但是没写出来

代码：

class Solution {
    List<String> res;   // 记录所有合法的括号组合

    public List<String> generateParenthesis(int n) {
        res = new ArrayList<>();
        backtrack(new StringBuilder(),n,n);   // 可用的左括号和右括号数量初始化为 n
        return res;
    }
// 可用的左括号数量为 cntl 个，可用的右括号数量为 cntr 个
    private void backtrack(StringBuilder sb,int cntl,int cntr){
         // 若左括号剩下的多，说明不合法 对于一个「合法」的括号字符串组合 p，必然对于任何 0 <= i < len(p) 都有：子串 p[0..i] 中左括号的数量都大于或等于右括号的数量。
        if(cntr<cntl) return;
          // 数量小于 0 肯定是不合法的
        if(cntl<0||cntr<0) return;
    // 当所有括号都恰好用完时，得到一个合法的括号组合
        if(cntl==0&&cntr==0){
            res.add(sb.toString());
            return;
        }
 // 尝试放一个左括号
        sb.append('(');   //选择
        backtrack(sb,cntl-1,cntr);
        sb.deleteCharAt(sb.length()-1);  //撤销选择
// 尝试放一个右括号
        sb.append(')');  //选择
        backtrack(sb,cntl,cntr-1);
        sb.deleteCharAt(sb.length()-1);  //撤销选择
    }
}