关于算法:回溯算法子集组合排列问题

作者：Rhythm_2019

创立工夫：2021.04.04

批改工夫：2021.04.05

Email：rhythm_2019@163.com

导读：本文次要讲述利用回溯算法生成数组的子集、组合和排列，三者都是在数组中一直做“抉择元素”、“递归”、“勾销抉择”三件事，依据题目的不同要求退出一些条件束缚（深度限度、判重）即可解决问题。文章最初总结了本人在写代码时所犯下的谬误，通过本文本人也对回溯算法有了信的了解

通过浏览本文您能够解答上面算法题：

1. LeetCode78. 子集
2. LeetCode90. 子集 II
3. LeetCode77. 组合
4. LeetCode46. 全排列
5. LeeCode47. 全排列 II

当然啦，最重要的是你在写回溯代码的时候的那种感觉，我在写代码的时候犯了很多谬误，都放在文章的最初啦

<hr/>

咱们先回顾一下什么是递归，简略来说就是本人调用本人，为什么本人调用本人就能解决问题呢？是因为问题存在反复的子问题，而且规模放大到最小时问题的解是已知的。

不用将分治、递归、回溯华清界线，就当本人在写递归即可

上面是递归的模板

private void recursion(int level, int maxLevel, int param) {
    // Terminator
    
    // Process
    
    // Drill down
    
    // Restore
}

回溯算法其实就是再下探 Drill down 后对数据进行复原，也就是Restore，从而达到一直试探但成果。在平时的算法练习中我常写递归，然而须要回溯的状况比拟少（可能是我写的不多），比拟常见的就是走迷宫（DFS 染色）、生成子集、N 皇后、数独等

子集

数组 [1, 2] 的子集有 []、[1]、[2]、[1, 2] 四个，大家重点注意一下回溯的解法，其余解法大家看看就好

LeetCode 78 子集

给定一个数组nums，生成其所有子集，我想到的思路有：

1. 自顶向下：已知 [0, i] 的所有子集，以后数字 2 能够抉择退出他们，抉择不退出他们，这样即可生成所有子集，咱们把这个办法称为抉择退出吧
2. 对于任意元素都有两种抉择，呈现在汇合里，不呈现在汇合里，这样就能生成所有子集，这个办法称之为抉择呈现吧
3. 回溯算法，别离对数组中的元素做选自、递归、勾销抉择

先是第一种抉择退出的思路

public List<List<Integer>> subsets(int[] nums) {if (nums.length == 0) {return new ArrayList<>();
    }
    return _subsets(nums.length - 1, nums);

}

public List<List<Integer>> _subsets(int level, int[] nums) {
    // Terminator
    if (level < 0) {List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>());
        return ans;
    }
    // Process & Drill dwon
    // 取得后面的所有子集
    List<List<Integer>> subsets = _subsets(level - 1, nums);

    int size = subsets.size();
    for (int i = 0; i < size; i++) {List<Integer> list = new ArrayList<>(subsets.get(i));
        list.add(nums[level]);
        subsets.add(list);
    }

    return subsets;
}

第二种抉择呈现的思路

private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> subsetsWithDup(int[] nums) {if (nums.length == 0) {return ans;}
    Arrays.sort(nums);
    _subsets(0, nums, new ArrayList<>(), new HashSet<>());
    return ans;
}
public void _subsets(int level, int[] nums, ArrayList<Integer> list) {
    // Terminator
    if (level == nums.length) {ans.add(list);
        return;
    }
    // Process & Drill down
    ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone();
    ArrayList<Integer> list2 = (ArrayList<Integer>) list.clone();
    
    // 呈现
    list1.add(nums[level]);
    _subsets(level + 1, nums, list1, res);
    // 不呈现
    _subsets(level + 1, nums, list2, res);
}

<hr/>

最初就是回溯算法，咱们应用循环别离对数组中的元素做抉择，调用递归函数，勾销抉择

private List<List<Integer>> ans = new ArrayList<>();

private List<List<Integer>> subsets(int[] nums) {if (nums.length == 0) {return ans;}
    _subsets(0, nums, new ArrayList<>());
    return ans;
}

private void _subsets(int level, int[] nums, ArrayList<Integer> list) {
    // 每一步都要保留后果
    ans.add(new ArrayList<>(list));

    for (int i = level; i < nums.length; i++) {
        //【抉择】list.add(nums[i]);
        //【递归】_subsets(i + 1, nums, list);
        //【勾销抉择】list.remove(level);
    }
}

将其状态树画进去，大略是这样子的。途中一行代表递归的层级，黄色示意须要被保留的后果

LeetCode 90 子集 II

我一开始以位间接加一个哈希表对反复元素进行剪枝即可，折腾了半天才发现问题

图上浅灰色方块示意应用哈希表剪枝的元素，比方最左边灰色的 1 因为和最后面的 1 反复了，咱们就不对他进行递归了。黄色示意后果，大家能够看到深灰色的两个元素反复了，这时因为蕴含反复元素，很天然的 [1, 2] 和[2, 1]是反复的只能保留一个

如果我对数组进行排序，问题就会失去解决

排序可能将反复元素放在一起，前面的元素就不会生成和后面数字相干的子集

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> subsetsWithDup(int[] nums) {if (nums.length == 0) {return ans;}
    Arrays.sort(nums);
    _subsets(0, nums, new ArrayList<>(), new HashSet<>());
    return ans;
}

private void _subsets(int level, int[] nums, ArrayList<Integer> list, Set<Integer> visited) {ans.add(new ArrayList<>(list));
    for (int i = level; i < nums.length; i++) {if (visited.contains(nums[i])) {continue;}
        visited.add(nums[i]);
        list.add(nums[i]);
        _subsets(i + 1, nums, list, new HashSet<>());
        list.remove(level);
    }
}

这里介绍了回溯的办法，咱们也能够应用抉择呈现现的思路，不过也是须要先排序，而后计算反复元素个数，如果就一个，依照以前的逻辑兵分两路，如果超过 n 个 (n > 1)，阐明存在反复元素，正确的逻辑应该是让数字呈现0 ~ n 次

private List<List<Integer>> ans = new ArrayList<>();

public List<List<Integer>> subsetsWithDup(int[] nums) {if (nums.length == 0) {return ans;}
    Arrays.sort(nums);
    _subsets(0, nums, new ArrayList<>(), new HashSet<>());
    return ans;
}

private void _subsets(int level, int[] nums, ArrayList<Integer> list, Set<Integer> visited) {
    // Terminator
    if (level >= nums.length) {ans.add(list);
        return;
    }
    // Process & Drill down
    int count = 1, index = level + 1;
    while (index < nums.length && nums[level] == nums[index]) {
        index++;
        count++;
    }
    if (count == 1) {
        // 没有反复
        ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone();
        ArrayList<Integer> list2 = (ArrayList<Integer>) list.clone();
        // 呈现
        list1.add(nums[level]);
        _subsets(level + 1, nums, list1, visited);
        // 不呈现
        _subsets(level + 1, nums, list2, visited);
    } else {
        // 存在反复
        ArrayList<Integer> list1 = (ArrayList<Integer>) list.clone();
        // 不呈现
        _subsets(level + count, nums, (ArrayList<Integer>) list1.clone(), visited);
        for (int i = 1; i <= count; i++) {list1.add(nums[level]);
            // 呈现 i 次
            _subsets(level + count, nums, (ArrayList<Integer>) list1.clone(), visited);
        }
    }
}

组合

以前看动静布局的时候始终没弄明确排列和组合的区别，那题 Coin Change i/ii 历历在目。对于一个数组 c 长度为 n，其组合有 C（n, m） 个，而排列数则有 A(n, m) 个

LeetCode 77 组合

子集蕴含所有组合的状况，入参 k 其实示意的是递归层数，所以咱们只须要在子集的根底上增加一个终止条件即可

private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> combine(int n, int k) {if (n < 0) {return ans;}

    _combine(0, 1, n, k, new ArrayList<>());
    return ans;
}

private void _combine(int level, int start, int n, int k, List<Integer> list) {if (level == k) {ans.add(list);
        return;
    }

    for (int i = start; i <= n - (k - list.size()) + 1; i++) {list.add(i);
        _combine(level + 1,  i + 1, n, k, new ArrayList<>(list));
        list.remove(level);
    }
}

大家看图

其实和子集的一毛一样，最左边灰色的 3 被剪枝的次要是因为他凑不到 2 个。

数组和数字的生成形式很相似，如果数组中存在反复元素置信大家都会解决了

不那么相干的题目还有：17. 电话号码的字母组合

排列

LeetCode 46 全排列

组合是子集的一部分，然而排列就不一样了，每次抉择都能选后面的元素但又不能选到本人，所以咱们能够创立一个哈希表来存储抉择过的元素（这里抉择保留其索引）

private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {if (nums == null || nums.length == 0) {return new ArrayList<>();
    }

    _permute(0,nums, new ArrayList<>(), new HashSet<>());
    return ans;
}

private void _permute(int level, int[] nums, List<Integer> List, Set<Integer> visited) {if (level == nums.length) {ans.add(List);
        return;
    }

    for (int i = 0; i < nums.length; i++) {if (visited.contains(i)) {continue;}
        visited.add(i);
        List.add(nums[i]);
        _permute(level + 1, nums, new ArrayList<>(List), visited);
        List.remove(nums[i]);
        visited.remove(i);
    }
}

画一下图大略就是这样

LeetCode 47 全排列 II

当初蕴含反复元素，咱们能够再创立一个哈希表用于记录以后层已应用过的元素，这样反复的元素就被剪枝

private List<List<Integer>> ans = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {if (nums == null || nums.length == 0) {return new ArrayList<>();
    }
    Arrays.sort(nums);
    _permute(0,nums, new ArrayList<>(), new HashSet<>());
    return ans;
}

private void _permute(int level, int[] nums, List<Integer> List, Set<Integer> indexVisited) {if (level == nums.length) {ans.add(List);
        return;
    }

    Set<Integer> contentVisited = new HashSet<>();
    for (int i = 0; i < nums.length; i++) {if (indexVisited.contains(i) || contentVisited.contains(nums[i])) {continue;}
        contentVisited.add(nums[i]);
        indexVisited.add(i);

        List.add(nums[i]);
        _permute(level + 1, nums, new ArrayList<>(List), indexVisited);
        List.remove(level);

        indexVisited.remove(i);
    }
}

这里波及两个哈希表：

1. indexVisited：用来记录递归时走过的元素，他保障了下一次递归不再拜访某元素，作用于全局，须要被始终传递的
2. contentVisited：用来保留某一层已遍历的元素，这样就能剪掉反复元素，作用域某一层级，所以不必传递

总结

这篇文章我大略写了两天，感觉还有些中央没说分明，我感觉要把算法思维正确的表达出来是一件不容易的事，还须要多加了解和练习。对于下面这几个题目其实套路都差不多

private void recursion() {
    // 终止条件，个别都是限定递归层数
    
    // 循环做抉择
    for (int i = start; i <= n; i++) {
        //【抉择】将后果放入数组
        //【递归】Drill down
        //【勾销抉择】将抉择移出数组
    }
}

总结一下须要留神的几个点：

1. 咱们写 for 循环的时候怎么写，应该从哪里开始到哪里完结：

   如果是子集和组合，为了不反复抉择本人之前抉择的元素，咱们应该指定开始下标，每进入一曾递归下标往后挪动。对于组合如果提米规定了输入组合的长度咱们能够适当剪枝。对于排列数，每次都能够选之前的元素，所以是从 0 开始

2. 什么时候须要引入 HashSet 判重：

   不蕴含反复元素：子集和组合是不须要的，因为通过开始下标咱们曾经排除了之前抉择过的元素。而排列数则须要记录递归路上抉择过的索引（元素值也能够），这样就不会反复选到之前选过的元素，这个哈希表须要全局应用，须要被传递

   蕴含反复元素：咱们须要应用 HashSet 对以后层的反复元素进行剪枝，这个哈希表只作用于以后层，不须要传递

   所以蕴含反复元素时须要应用哈希表，而排列数原本就肯定须要哈希表

3. 对于后果 list 的传递需不需要 clome：当然须要，咱们最好应用构造方法创立新的，而且要留神创立的机会，肯定是创立后马上退出后果集，两头不能有任何add 和remove操作

4. 最初想说的是留神【抉择】和【撤销抉择】的形式，我已经是这样写的代码

   private void _combine(int level, int start, int n, int k, List<Integer> list) {
      // ...
   
       for (int i = start; i <= n - (k - list.size()) + 1; i++) {list.add(i);
           _combine(level + 1,  i + 1, n, k, new ArrayList<>(list));
           // 留神这里
           list.remove(new Integer(i));
       }
   }

   这样写在元素不反复的状况下是没什么问题的，然而如果存在反复元素的话递归时会删掉第一个反复的元素，所以咱们间接这样写

   list.add(i);
   _combine(level + 1,  i + 1, n, k, new ArrayList<>(list));
   // 留神这里
   list.remove(level);

   这样删除元素才正确

<hr/>

我集体感觉算法挺有意思的，本人也听喜爱写题，细想一下可能是因为这些题目规模较小，但十分微妙，你的代码让计算机变得灵便，学习老本也不会太高，所以我更喜爱算法。

之前面试遇到的一个题目，如何正确计算0.3 / 0.2 ，曾经脱了很久了，前面会给大家带来告计算机的小数和高精算法的内容，还有十分神奇的卡特兰数，大家能够期待一下。