【LeetCode】﹝回溯法ி﹞ 全排列、子集、组合问题

╰+哭是因爲堅強的太久メ 2022-12-27 04:58 252阅读 0赞

### 文章目录 ###

*   *   *  一、全排列
         *   *  1.1 无重复元素全排列
             *   *  1.1.1 从左向右交换
                 *  1.1.2 从右往左交换
                 *  1.1.3 移动元素至左（升序排列）
                 *  1.1.4 移动元素至右（\`逆序看\`降序排列）
                 *  【拓展】康托展开
             *  1.2 有重复元素全排列
         *  二、子集
         *   *  2.1 无重复元素子集
             *   *  2.1.1 回溯法
                 *  2.1.2 二进制计数法
                 *  2.1.3 迭代法
             *  2.2 有重复元素子集
             *   *  2.2.1 回溯法
                 *  2.2.2 迭代法
         *  三、组合
         *   *  3.1 组合
             *  3.2 组合总和
             *  3.3 组合总和IV
         *  四、总结

--------------------

### 一、全排列 ###

#### 1.1 无重复元素全排列 ####

[LeetCode全排列][LeetCode]

**给定一个没有重复数字的序列，返回其所有可能的全排列**

//示例   输入[1, 2, 3]
    /*输出    
    [
      [1,2,3],
      [1,3,2],
      [2,1,3],
      [2,3,1],
      [3,1,2],
      [3,2,1]
    ]
    */

##### 1.1.1 从左向右交换 #####

观察元组 **\[1, 2, 3\]**，以元素1为第一位的排列有 **\[1, 2, 3\]** 和 **\[1, 3, 2\]**，此排列可以由初始排列和交换2和3后得到。以元素2为第一位的元素排列有 **\[2, 1, 3\]** 和 **\[2, 3, 1\]** ，同样以元素3为第一位的排列有 **\[3, 2, 1\]** (`此处是321而不是312的原因是按下面代码执行顺序来的，因为先交换了3和1，不同的交换顺序或者操作不同生成的全排列顺序不同，但其组成的集合是相同的，其他的顺序下面会讲到`) 和 **\[3, 1, 2\]**

在函数backtrack()中，循环中i初始值为begin是因为要将自己与自己交换来保存当前这个序列，之后深度搜索递归处理交换位置从begin+1开始，递归结束后恢复现场，将交换的数交换回来，继续循环交换处理第i+1个数据。

class Solution {
        
        List<List<Integer>> res;
        public List<List<Integer>> permute(int[] nums) {
        
            res = new ArrayList();
            List<Integer> temp = new ArrayList<>();
            for(int i : nums){
        
                temp.add(i);
            }
            backtrack(temp, 0, nums.length);
            return res;
        }
        public void backtrack(List<Integer> temp, int begin, int end){
        
            if(begin == end){
        
                res.add(new ArrayList<>(temp));
                return;
            }
            for(int i = begin; i < end; i++){
        
                Collections.swap(temp, begin, i);
                backtrack(temp, begin + 1, end);
                Collections.swap(temp, begin, i);
            }
        }
    }

在主函数中调用如下

Solution so = new Solution();
    List list = so.permute(new int[] {
        1, 2, 3});
    for(Object temp : list) {
        
    	System.out.println(temp);
    }

输出结果如下图所示，可看出第一个元素依次是1， 2， 3  
![在这里插入图片描述][20201208110310450.jpg_pic_center]

##### 1.1.2 从右往左交换 #####

若将for循环修改为从end至begin交换

//backtrack(temp, 0, nums.length - 1);
    public void backtrack(List<Integer> temp, int begin, int end){
        
        if(begin == end){
        
            res.add(new ArrayList<>(temp));
            return;
        }
        for(int i = end; i >= begin; i--){
        
            Collections.swap(temp, i, end);
            backtrack(temp, begin, end - 1);
            Collections.swap(temp, i, end);
        }
    }

输入结果如下图所示，可看出最后一个元素依次是3，2，1

![在这里插入图片描述][20201208110346435.jpg_pic_center]

##### 1.1.3 移动元素至左（升序排列） #####

若将第i个元素移动至begin前面，返回的序列正好是按其升序排列的序列，可对比从左向右交换的方法

for(int i = begin; i < end; i++){
        
        int t = temp.remove(i);
        temp.add(begin, t);
        backtrack(temp, begin + 1, end);
        temp.remove(begin);
        temp.add(i, t);
    }

输入结果如下图所示，可看出其结果按升序排列

![在这里插入图片描述][20201208110416279.jpg_pic_center]

##### 1.1.4 移动元素至右（`逆序看`降序排列） #####

若将第i个元素移动至end后面，返回的正好是按其序列逆序降序排列的序列，可以对比从右往左交换的方法

for(int i = end; i >= begin; i--){
        
        int t = temp.remove(i);
        temp.add(end, t);
        backtrack(temp, begin, end - 1);
        temp.remove(end);
        temp.add(i, t); 
    }

输入结果如下图所示

![在这里插入图片描述][2020120811043737.jpg_pic_center]

##### 【拓展】康托展开 #####

[LeetCode排列序列][LeetCode 1]

输入n和k，返回1-n按其升序排列的第k个排列序列

按大小顺序列出所有排列情况，并一一标记，当 `n = 3` 时, 所有排列如下：

1.  `"123"`
2.  `"132"`
3.  `"213"`
4.  `"231"`
5.  `"312"`
6.  `"321"`

当k = 4时应输出“231”

**解题方法**：此问题可以用上面讲到的第三种方法找到第k个后终止搜索并返回结果就可以了，但比较耗时。可以用下面的数学方法康托展开来解这道题。

`康托展开`是一个全排列到一个自然数的双射，常用于构建哈希表时的时间压缩。康拓展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的  
 X = a n ( n − 1 ) ! + a ( n − 1 ) ( n − 2 ) ! + ⋯ + a 1 0 ! X= a\_n (n-1)!+a\_(n-1) (n-2)!+⋯+a\_1 0! X=an(n−1)!\+a(n−1)(n−2)!\+⋯\+a10!  
其中，ai为整数，并且0<=ai<i, 1< =i <= n，ai表示原数的第i位在当前未出现的元素中是排在第几个，详细见链接

[康托展开搜狗百科][Link 1]

class Solution {
        
        public String getPermutation(int n, int k) {
        
            int[] factor = new int[n];
            factor[0] = 1;
            for(int i = 1; i < n; i++) {
        
                factor[i] = factor[i - 1] * i;
            }
            ArrayList<Integer> list = new ArrayList<>();
            for(int i = 1; i <= n; i++) {
        
                list.add(i);
            }
            k--;
            StringBuffer sb = new StringBuffer();
            for(int i = n - 1; i >= 0; i--) {
        
                int t = k / factor[i];
                sb.append(list.remove(t));
                k %= factor[i];
            }
            return sb.toString();
        }
    }

#### 1.2 有重复元素全排列 ####

[LeetCode全排列II][LeetCode_II]

给定一个可包含重复数字的序列 `nums` ，**按任意顺序** 返回所有不重复的全排列

/*输入：nums = [1,1,2]
    输出：
    [[1,1,2],
     [1,2,1],
     [2,1,1]]
     */

将此数组元素加入ArrayList中，在每次遍历元素前判断此元素之前是否已经被交换过，若之前有相同的元素已经交换了，则跳过此元素。此过程可以用HashSet来实现。就是在上述1.1从左向右交换中使用HashSet，具体代码如下

public void backtrack(List<Integer> list, int begin, int end){
        
        if(begin == end){
        
            res.add(new ArrayList(list));
            return;
        }
        Set<Integer> set = new HashSet<>();
        for(int i = begin; i < end; i++){
        
            if(set.contains(list.get(i))){
        
                continue;
            }
            set.add(list.get(i));
            Collections.swap(list, begin, i);
            backtrack(list, begin + 1, end);
            Collections.swap(list, begin, i);
        }
    }

对于数组\[1, 1, 2, 2\]，程序运行结果如下图所示  
![在这里插入图片描述][20201208111741660.jpg_pic_center]

--------------------

### 二、子集 ###

#### 2.1 无重复元素子集 ####

[LeetCode子集][LeetCode 2]

给定一组**不含重复元素**的整数数组 *nums*，返回该数组所有可能的子集（幂集）

【注意】 解集不能包含重复的子集

//输入 nums = [1, 2, 3]
    /*输出
      [3],
      [1],
      [2],
      [1,2,3],
      [1,3],
      [2,3],
      [1,2],
      []
    */

##### 2.1.1 回溯法 #####

空集必定包含在子集中，可以初始化list为空，所以backtrack()函数开始时应在结果集中加入list，然后从begin开始每次遍历一个元素将其加入到list中，深度遍历的下一步是遍历第i+1个元素（因为已经加入了第i个元素，此时递归加入第i+1个元素），最后一步状态重置移除刚刚加入的第i个元素。然后继续循环处理第i+1个元素。`此处使用LinkedList方便添加和删除`

class Solution {
        
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> subsets(int[] nums) {
        
            backtrack(nums, new LinkedList<Integer>(), 0);
            return res;
        }
        public void backtrack(int[] nums, LinkedList<Integer> list, int begin){
        
            res.add(new LinkedList<Integer>(list));
            for(int i = begin; i < nums.length; i++) {
        
            	list.add(nums[i]);
            	backtrack(nums, list, i + 1);
            	list.removeLast();
            }
        }
    }

调用程序nums = \[1, 2, 3\]的输出结果如下图所示

![在这里插入图片描述][20201208111826987.jpg_pic_center]

##### 2.1.2 二进制计数法 #####

对于 nums = \[1, 2, 3\]来说，有三个元素，则包含的子集个数为2^3 = 8个，此八个子集分别为0 - 7对应的二进制中相应位置为1的元素组合，如下示例

/*
       321
    0  000  []
    1  001  [1]
    2  010  [2]
    3  011  [2, 1]
    4  100  [3]
    5  101  [3, 1]
    6  110  [3, 2]
    7  111  [3, 2, 1]
    */

所以可以遍历0-7的数字，根据对应二进制位的数字为1（或0）来决定加入（不加入）对应元素，具体代码如下

class Solution {
        
        public List<List<Integer>> subsets(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<>();
            int n = (1 << nums.length);
            for(int i = 0; i < n; i++){
        
                List<Integer> list = new ArrayList<>();
                int x = i;
                for(int j = 0; j < nums.length; j++){
        
                    if((x & 1) == 1){
        
                        list.add(nums[j]);
                    }
                    x >>= 1;
                }
                res.add(list);
            }
            return res;
        }
    }

输出结果res如下图所示

![在这里插入图片描述][20201208111900816.jpg_pic_center]

##### 2.1.3 迭代法 #####

可以先将空集加入结果集，然后每遍历一个元素，将此元素加入结果集的每个子集中形成新的集合，将此集合加入到结果集中，直至遍历完最后一个元素，详细过程如下

/*
    []
    [1]
    [2]
    [1, 2]
    [3]
    [1, 3]
    [2, 3]
    [1, 2, 3]
    */

具体代码如下

class Solution {
        
        public List<List<Integer>> subsets(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<>();
            res.add(new ArrayList<Integer>());
            for(int x : nums){
        
                int len = res.size();
                for(int i = 0; i < len; i++){
        
                    List<Integer> list = new ArrayList(res.get(i));
                    list.add(x);
                    res.add(list);
                }
            }
            return res;
        }
    }

程序输出结果如下

![在这里插入图片描述][20201208111931380.jpg_pic_center]

#### 2.2 有重复元素子集 ####

[LeetCode子集II][LeetCode_II 1]

给定一个可能包含重复元素的整数数组 ***nums***，返回该数组所有可能的子集（幂集）

【注意】解集不能包含重复的子集

/*
    输入: [1,2,2]
    输出:
    [
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]
    */

##### 2.2.1 回溯法 #####

**首先要进行排序，之后再用HashSet去重**。若不进行排序，对于像\[4, 4, 4, 1, 4\]这样的序列，因为每次回溯过程中会移除当前元素，假如在移除了第三个4后遍历到最后一个4，会重复记录\[4, 4, 1, 4\]。

`对于有重复元素的全排列来说，不需要排序，因为它的集合是所有元素的组合`

class Solution {
        
    	List<List<Integer>> res;
        public List<List<Integer>> subsetsWithDup(int[] nums) {
        
            Arrays.sort(nums);
            res = new ArrayList<>();
            backtrack(nums, new ArrayList<Integer>(), 0);
            return res;
        }
        private void backtrack(int[] nums, List<Integer> list, int begin) {
        
        	res.add(new ArrayList<Integer>(list));
        	Set<Integer> set = new HashSet<>();
        	for(int i = begin; i < nums.length; i++) {
        
        		if(set.contains(nums[i])) {
        
        			continue;
        		}
        		set.add(nums[i]);
        		list.add(nums[i]);
        		backtrack(nums, list, i + 1);
        		list.remove(list.size() - 1);
        	}
        }
    }

对于数组nums = \[4, 4, 4, 1, 4\]执行结果如下图所示

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]

##### 2.2.2 迭代法 #####

首先要进行**排序**

和无重复元素中的迭代法一样，假如nums = \[1, 2, 2, 3\]，根据前面的迭代若此时结果集中元组为\[\[\], \[1\], `[2], [1, 2]`\]，且\[2\]和\[1, 2\]是遍历第一个2时生成的，此时在遍历第二个2时，对\[\]和\[1\]不需重新加入了，只需在遍历前面2的生成的子集基础上加入2，即得到 **\[2, 2\]** 和 **\[1, 2, 2\]** 。因此需要记录每次新生成的子集数，若当前元素与前一个元素不相等，则结果集从0开始处理；若相同，则从（list.size() - count）处开始处理。具体见代码和运行结果分析。

class Solution {
        
        public List<List<Integer>> subsetsWithDup(int[] nums) {
        
            List<List<Integer>> res = new ArrayList<>();
            res.add(new ArrayList<Integer>());
            Arrays.sort(nums);
            int count = 0;
            for(int i = 0; i < nums.length; i++){
        
                int begin = 0;
                if(i != 0 && nums[i] == nums[i - 1]){
        
                    begin = res.size() - count;
                }
                int len = res.size();
                count = 0;
                for(int j = begin; j < len; j++){
        
                    List<Integer> list = new ArrayList<>(res.get(j));
                    list.add(nums[i]);
                    res.add(list);
                    count++;
                }
            }
            return res;
        }
    }

运行结果和分析如下

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]

--------------------

### 三、组合 ###

#### 3.1 组合 ####

[LeetCode组合][LeetCode 3]

给定两个整数 *n* 和 *k*，返回 1 … *n* 中所有可能的 *k* 个数的组合

/*
    输入: n = 4, k = 2
    输出:
    [
      [2,4],
      [3,4],
      [2,3],
      [1,2],
      [1,3],
      [1,4],
    ]
    */

组合其实就是在子集问题的基础上增加了约束条件，使得子集中元素的长度为k。所以可以在选择将集合加入结果集时判断是否等于要求个数k，可以通过剪枝提高效率，若当前集合元素个数加上未遍历元素个数小于k，剩余元素没必要判断了。

class Solution {
        
        List<List<Integer>> res = new LinkedList<>();
        public List<List<Integer>> combine(int n, int k) {
        
            backtrack(new LinkedList<Integer>(), 1, n, k);
            return res;
        }
        public void backtrack(LinkedList<Integer> list, int begin, int n, int k){
        
            if(n - begin + 1 < k){
        
                return;
            }
            if(k == 0){
        
                res.add(new LinkedList<>(list));
                return;
            }
            for(int i = begin; i <= n; i++){
        
                list.add(i);
                backtrack(list, i + 1, n, k - 1);
                list.removeLast();
            }
        }
    }

对于示例 n = 4, k = 2 时执行程序输出结果如下图所示

![在这里插入图片描述][20201208112100258.jpg_pic_center]

#### 3.2 组合总和 ####

[LeetCode组合总和][LeetCode 4]

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以**无限制重复被选取**。

**说明**：

所有数字（包括 target）都是正整数  
解集不能包含重复的组合

/*输入：candidates = [2,3,6,7], target = 7,
    所求解集为：
    [
      [7],
      [2,2,3]
    ]
    */

因为数组中的数字可以重复选取，所以在递归调用backtrack函数时begin是从i开始，表示还是从当前元素判断，直到target < 0（即目标和大于给定初始值target）为止。具体代码如下所示（此处只给出backtrack( )函数）

public void backtrack(int[] candidates, LinkedList<Integer> list ,int begin, int end, int target){
        
        if(target < 0){
        
            return;
        }
        if(target == 0){
        
            res.add(new LinkedList(list));
            return;
        }
        for(int i = begin; i < end; i++){
        
            list.add(candidates[i]);
            backtrack(candidates, list, i, end, target - candidates[i]);
            list.removeLast();
        }
    }

对于 candidates = \[1, 2, 3\]， target = 6应用程序输出结果如下图

![在这里插入图片描述][20201208112122595.jpg_pic_center]

#### 3.3 组合总和IV ####

[LeetCode组合总和IV][LeetCode_IV]

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数

/*
    nums = [1, 2, 3]
    target = 4
    输出： 7
    所有可能的组合为：
    (1, 1, 1, 1)
    (1, 1, 2)
    (1, 2, 1)
    (1, 3)
    (2, 1, 1)
    (2, 2)
    (3, 1)
    请注意，顺序不同的序列被视作不同的组合
    */

因为不同的顺序被视为不同的组合，此问题是**组合和全排列的结合**，使用回溯法可以先求出和为目标数的子集（哈希表**去重排序后的子集**），然后求子集的全排列个数，之后相加便是。

但这道题使用动态规划可以很简单地解决，相关代码如下

class Solution {
        
        public int combinationSum4(int[] nums, int target) {
        
            int[] dp = new int[target + 1];
            dp[0] = 1;
            for(int i = 1; i <= target; i++){
        
                for(int j : nums){
        
                    if(i >= j){
        
                        dp[i] += dp[i - j];
                    }
                }
            }
            return dp[target];
        }
    }

### 四、总结 ###

类似的题目有字母的全排列、字母的子集，组合总和II，组合总和III······

相信你只要认真读过上述所有题解，下次遇到类似的题目一定会清晰快速地完成！

[LeetCode]: https://leetcode-cn.com/problems/permutations/
[20201208110310450.jpg_pic_center]: /images/20221120/22c6ac1d57b942b1933eaa8c23ca3f65.png
[20201208110346435.jpg_pic_center]: /images/20221120/7f61fe47582c4311910e18e4b868352f.png
[20201208110416279.jpg_pic_center]: /images/20221120/156793874a27407789857369b2e5cab9.png
[2020120811043737.jpg_pic_center]: /images/20221120/48d4263fd5454d5c8b17412e0b4b34da.png
[LeetCode 1]: https://leetcode-cn.com/problems/permutation-sequence/
[Link 1]: https://baike.sogou.com/v55671042.htm?fromTitle=%E5%BA%B7%E6%89%98%E5%B1%95%E5%BC%80
[LeetCode_II]: https://leetcode-cn.com/problems/permutations-ii/
[20201208111741660.jpg_pic_center]: /images/20221120/9a453a7e2f4946a68833247109d5b794.png
[LeetCode 2]: https://leetcode-cn.com/problems/subsets/
[20201208111826987.jpg_pic_center]: /images/20221120/c5861d177dbd40f2acb6089d103e11c6.png
[20201208111900816.jpg_pic_center]: /images/20221120/9528dacc1b02409e934ca8daad9fe0e7.png
[20201208111931380.jpg_pic_center]: /images/20221120/0da2314441d043b49878699b773515d7.png
[LeetCode_II 1]: https://leetcode-cn.com/problems/subsets-ii/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/4fe6dc422d9c4f08b52c000f0b5f3ad8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDM2ODQzNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/a26efb5bcc38405a8fdc02be412eea5b.png
[LeetCode 3]: https://leetcode-cn.com/problems/combinations/
[20201208112100258.jpg_pic_center]: /images/20221120/4946fb44f5a14837b3b021d35cf484a1.png
[LeetCode 4]: https://leetcode-cn.com/problems/combination-sum/
[20201208112122595.jpg_pic_center]: /images/20221120/543c265585de4aba99888106ce4f03a8.png
[LeetCode_IV]: https://leetcode-cn.com/problems/combination-sum-iv/