回溯系列一之排列组合与子集系列

柔情只为你懂 2022-12-05 00:56 161阅读 0赞

### 文章目录 ###

*   *  排列，组合，子集
     *   *  全排列
         *   *  题目
             *  思考
             *  代码
         *  全排列II
         *   *  题目
             *  思考
             *  代码
         *  组合总和
         *   *  题目
             *  思想
             *  代码
             *   *  优化
         *  组合总和-II
         *   *  题目
             *  思想
             *  代码
             *   *  优化一：
                 *  优化二
         *  组合
         *   *  题目
             *  思路
             *  代码
         *  子集
         *   *  题目
             *  思路
             *  代码
         *  子集-II
         *   *  题目
             *  思路
             *  代码

## 排列，组合，子集 ##

*  排列问题：由于要记录哪一些数字已经被选择过，好让以后能正确选到未选择的数，因此需要设置 `visited` 数组；
 *  组合问题：由于不强调顺序，包含了一个数字的所有组合得到以后，下一轮搜索就不能再含有这个数字，否则会出现重复。因此需要设置搜索起点 `begin`。

### 全排列 ###

#### 题目 ####

[46-全排列][46-]

![image-20200908165813521.png][]

#### 思考 ####

此题目就是最为经典的回溯问题，利用递归来找出我们要的结果，对于此题的递归树而言如下图所示（图片来源）

![image-20200908170110181.png][]

此题为排列问题，对于所有的值给定我们，需要我们做的是对其进行重新的排列处理，对于系列的问题需要注意的是对于元素判断是否在当前的循环中已经访问过所以需要设置一个是否访问数组：

#### 代码 ####

public List<List<Integer>> permute(int[] nums) { 
     List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            boolean [] visited = new boolean[nums.length];
            dfs(0,nums,list,lists,visited);
            return  lists;
        }
        private  static  void dfs(int start,int []nums,List<Integer> list,List<List<Integer>> lists,boolean[] visited){ 
            if(start == nums.length)
            { 
                lists.add(new ArrayList<>(list));
                return;
            }
            for(int i =0;i<nums.length;i++){ 
                if(!visited[i]){ 
                    visited[i] = true;
                    list.add(nums[i]);
                    dfs(start+1,nums,list,lists,visited);
                    visited[i] = false;
                    list.remove(list.size()-1);
                }
            }
        }

### 全排列II ###

#### 题目 ####

[全排列II][II]

![image-20200908170911500.png][]

#### 思考 ####

同上面的题目几乎是相同的，但是注意的是对于重复元素的处理。

利用到如下代码进行甄别。其中的`visited[i-1] == false`，是为了防止删除同一层中的相同的元素。

if(i>0 && nums[i]==nums[i-1] &&visited[i-1] == false)
                    { 
                        continue;
                    }

#### 代码 ####

public List<List<Integer>> permuteUnique(int[] nums) { 
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            boolean [] visited = new boolean[nums.length];
            Arrays.sort(nums);
            dfs(0,nums,list,lists,visited);
            return  lists;
    
        }
        private  static void dfs(int start,int [] nums,List<Integer> list,List<List<Integer>> lists,boolean [] visited){ 
            if(list.size() == nums.length){ 
                lists.add(new ArrayList<>(list));
                return;
            }
    
            for(int i = 0;i<nums.length;i++){ 
                if(!visited[i]){ 
    
                      if(i>0 && nums[i]==nums[i-1] &&visited[i-1] == false)
                    { 
                        continue;
                    }
                    visited[i] = true;
                    list.add(nums[i]);
                    dfs(start+1,nums,list,lists,visited);
                    visited[i] = false;
                    list.remove(list.size()-1);
                }
    
            }
        }

### 组合总和 ###

#### 题目 ####

[39-组合总和][39-]

![image-20200908141646833.png][]

#### 思想 ####

也算是典型的回溯系列的题解分析，对于此题目是`组合系列`，所谓的组合系列就是说，给定我们一个数组，让我们能够找出来特定的几个满足条件的存在。对于组合需要关注的在于。

由于顺序无关紧要，因此一个数有没有被选过很重要，因此需要设置搜索起点。

对于此题目来说，认为数字是可以重复使用，所以在完成了一个计算值的加入之后，例如对于`2`d的加入之后，我们并不需要说像是平常那样立马就对下一个元素进行遍历，就是在回溯里面对传递的参数进行加一处理,例如全排列中：需要进行加一处理是因为选中当前值之后，就需要进行以下值的挑选。

dfs(i + 1, nums, list, lists, visited);

但是本题中不需要进行此步操作，是因为还会可能进行元素的重复选择。

此时我们画出对应的树形解析图：

![image-20200908143544738.png][]

说明：

1.  以我们的和值作为根节点，创建分支来做减法。
2.  选中当前元素，存放到路径中，下一轮的循环中还是以当前值出发，因为可能会得到重复的元素来组成最后的值。
3.  判断在什么时候推出循环是关键点所在。
    
     *  对于不断减去当前元素的`target`来说,等于零的时候，表示当前路径下的值可以满足要求，记录下来。
     *  对于小于零的情况，表示不符合条件，进行返回即可。

#### 代码 ####

private static List<List<Integer>> combinationSum(int[] candidates, int target) { 
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
    
            dfs(candidates,target,lists,list);
            return  lists;
        }
    
        private  static  void dfs(int [] nums,int target,List<List<Integer>>lists,List<Integer> list){ 
            if(target<0)
                return;
            if(target== 0){ 
                lists.add(new ArrayList<>(list));
                return;
            }
            for(int i = 0;i<nums.length;i++){ 
           
                list.add(nums[i]);
                dfs(nums,target-nums[i],lists,list);
                list.remove(list.size()-1);
            }
        }
    
    //测试
       public static void main(String[] args) { 
            int [] nums = { 2,3,6,7};
            List<List<Integer>> lists = combinationSum(nums,7);
            System.out.println(lists);
        }

##### 优化 #####

但是上面代码会出现重复的计算结果：

![image-20200908150258736.png][]

这个时候我们只需要在每一次进行开始的搜索设置下一次开始的起点，因为就算是可以使用重复的元素的时候，进行下一轮的循环的时候，就会出现重复的值，所以进行小小的修改即可。

public List<List<Integer>> combinationSum(int[] candidates, int target) { 
        List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
    
            dfs(0,candidates,target,lists,list);
            return  lists;
        }
    
        private  static  void dfs(int start,int [] nums,int target,List<List<Integer>>lists,List<Integer> list){ 
     
            if(target<0)
                return;
            if(target== 0){ 
                lists.add(new ArrayList<>(list));
                return;
            }
            for(int i = start;i<nums.length;i++){ 
                list.add(nums[i]);
                dfs(i,nums,target-nums[i],lists,list);
                list.remove(list.size()-1);
            }
        }

### 组合总和-II ###

[40-组合总和][40-]

#### 题目 ####

![image-20200908160509705.png][]

#### 思想 ####

和前一题如出一辙，只不过变换的是，对于上面的一题是对于元素是可以重复使用的，就是我们可以对同一个元素多次使用，只要最后的结果是正确的即可。但是此题却不允许对元素进行重复的使用，有了上面第一题的讲解之后，我们心想，那还不简单，对于前面的一题，在参数传递时候并没有对每一次的循环进行选中下一个元素，这里我们选中下一个元素就好了。

#### 代码 ####

private static List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            Arrays.sort(candidates);
            dfs(0,candidates,target,lists,list);
            return  lists;
        }
    
        private  static  void dfs(int start,int [] nums,int target,List<List<Integer>>lists,List<Integer> list){ 
    
            if(target<0)
                return;
            if(target== 0){ 
                lists.add(new ArrayList<>(list));
                return;
            }
            for(int i = start;i<nums.length;i++){ 
                list.add(nums[i]);
                dfs(i+1,nums,target-nums[i],lists,list);
                list.remove(list.size()-1);
            }
        }
        public static void main(String[] args) { 
            int [] nums = { 10,1,2,7,6,1,5};
            List<List<Integer>> lists =combinationSum2(nums,8);
            System.out.println(lists);
        }

##### 优化一： #####

进行测试运行发现了问题所在：很明显，是对于两个1值进行了重复的判断。

[[1, 1, 6], [1, 2, 5], [1, 7], [1, 2, 5], [1, 7], [2, 6]]

这里就思考到我们[全排列-II][II]中的思想【这里后续贴出地址。】，对于元素添加已经访问的标签，然后利用是否访问来规避掉重复数的重复访问。代码如下：

private static List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            Arrays.sort(candidates);
            boolean [] visited = new boolean[candidates.length];
            dfs(0,candidates,target,visited,lists,list);
            return  lists;
        }
        private  static  void dfs(int start,int [] nums,int target,boolean [] visited,List<List<Integer>>lists,List<Integer> list){ 
            if(target<0)
                return;
            if(target== 0){ 
                lists.add(new ArrayList<>(list));
                return;
            }
            for(int i = start;i<nums.length;i++){ 
                if(!visited[i]){ 
                    // 这里的处理和全排列II中的处理重复元素是相同的。
                    if(i>0 && nums[i]==nums[i-1]&& visited[i-1]== false){ 
                        continue;
                    }
                    visited[i] =true;
                    list.add(nums[i]);
                    dfs(i+1,nums,target-nums[i],visited,lists,list);
                    visited[i] =false;
                    list.remove(list.size()-1);
                }
            }
        }
        public static void main(String[] args) { 
            int [] nums = { 10,1,2,7,6,1,5};
            List<List<Integer>> lists =combinationSum2(nums,8);
            System.out.println(lists);
        }

##### 优化二 #####

但是我们要明白的是对于全排列问题和组合总和问题的原理是截然不同的：

对于全排列问题可以称作是排列问题，就是数据都存在，我们进行全新的排列。

*  **排列问题**：由于要记录哪一些数字已经被选择过，好让以后能正确选到未选择的数，因此需要设置 `visited` 数组；

但是对于组合总和问题，被称作是组合问题，就是最开始是一无所有的，我么来选中部分的值来记录进结果里面。

*  **组合问题**：由于不强调顺序，包含了一个数字的所有组合得到以后，下一轮搜索就不能再含有这个数字，否则会出现重复。因此需要设置搜索起点 `begin`。

所以来说还是不要使用到是否访问过的`Boolean`类型的数组，而是想办法能不能直接进行对于再排序完成之后相同的进行删除呢？

private static List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            Arrays.sort(candidates);
            dfs(0,candidates,target,lists,list);
            return  lists;
        }
    
        private  static  void dfs(int start,int [] nums,int target,List<List<Integer>>lists,List<Integer> list){ 
    
            if(target<0)
                return;
            if(target== 0){ 
                lists.add(new ArrayList<>(list));
                return;
            }
            for(int i = start;i<nums.length;i++){ 
                // 注意不同点在于 这里我们没有设置是否访问过的数组，而是直接对相同的进行不处理。
                if(i>0 &&nums[i] ==nums[i-1])
                { 
                    continue;
                }
                list.add(nums[i]);
                dfs(i+1,nums,target-nums[i],lists,list);
                list.remove(list.size()-1);
            }
        }
        public static void main(String[] args) { 
            int [] nums = { 10,1,2,7,6,1,5};
            List<List<Integer>> lists =combinationSum2(nums,8);
            System.out.println(lists);
        }

结果,可以看到本来对于 `[1,1,6]`的正确结果，但是却被我们删除掉。

[[1, 2, 5], [1, 7], [2, 6]]

是因为我们直接进行略过操作，但是却不在乎是否是正确的结果。因为我们在出现重复结果时候，是因为对于第一个1计算一遍之后，相邻的第二个一又计算一遍，但是两者是在不同的层级里面（这里可以参考[全排列II][II 1]里面的具体讲解，关于层级和访问过于暂时没有访问过的概念)。所以我们只是想，在第二次遇到`1`的时候，判断其前面的值是否与其相等，如何第二次遇见呢？ 是我们在回溯的时候造成的，也就是不同的层级（对于一个for循环来说，以此向下的时候就是一个层级），于是我们简单进行修改操作，让我们想要判断的两个值在不同的层级，并且还相等的时候，就表示两者之间只能存在一个。

代码如下：

private static List<List<Integer>> combinationSum2(int[] candidates, int target) { 
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            Arrays.sort(candidates);
            dfs(0,candidates,target,lists,list);
            return  lists;
        }
    
        private  static  void dfs(int start,int [] nums,int target,List<List<Integer>>lists,List<Integer> list){ 
    
            if(target<0)
                return;
            if(target== 0){ 
                lists.add(new ArrayList<>(list));
                return;
            }
            for(int i = start;i<nums.length;i++){ 
                if(i>start &&nums[i] ==nums[i-1])
                { 
                    continue;
                }
                list.add(nums[i]);
                dfs(i+1,nums,target-nums[i],lists,list);
                list.remove(list.size()-1);
            }
        }
        public static void main(String[] args) { 
            int [] nums = { 10,1,2,7,6,1,5};
            List<List<Integer>> lists =combinationSum2(nums,8);
            System.out.println(lists);
        }

### 组合 ###

#### 题目 ####

[77-组合][77-]

![image-20200908171623606.png][]

#### 思路 ####

基础的回溯算法题目，注意起始点，和进行终止的点。

#### 代码 ####

public List<List<Integer>> combine(int n, int k) { 
        List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list  = new ArrayList<>();
            if(k>n)
                return  lists;
           dfs(1,n,k,list,lists);
            return  lists;
        }
        private  static void dfs(int start,int n,int k,List<Integer> list,List<List<Integer>>lists){ 
         if(k == list.size()){ 
             lists.add(new ArrayList<>(list));
             return;
         }
         for(int i = start ;i<= n-(k-list.size())+1;i++){ 
             list.add(i);
             dfs(i+1,n,k,list,lists);
             list.remove(list.size()-1);
         }
        }

### 子集 ###

#### 题目 ####

[78-子集][78-]

![image-20200908194002605.png][]

#### 思路 ####

有点全排列的影子，但是对于全排列而言，有其的限制（就是对于list）中的值要达到数组的长度。但是在子集里面就不需要进行限制，对于所有的情况都收录在里面，模板还是回溯的模板。

#### 代码 ####

private static List<List<Integer>> subsets(int[] nums) { 
    
            List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
            Arrays.sort(nums);
            dfs(0,nums,list,lists);
            return  lists;
        }
        private  static  void dfs(int index,int [] nums,List<Integer> list,List<List<Integer>> lists){ 
            lists.add(new ArrayList<>(list));
            for(int i = index;i<nums.length;i++){ 
                if(i>index && nums[i]==nums[i-1])
                { 
                    continue;
                }
                list.add(nums[i]);
                dfs(i+1,nums,list,lists);
                list.remove(list.size()-1);
            }
        }

### 子集-II ###

#### 题目 ####

[90-子集II][90-_II]

![image-20200908195641352.png][]

#### 思路 ####

与基本的子集的思想相同，对于所有的情况都记录在内，但是需要进行剪枝操作。对于不同层级且相邻相同时候，要进行舍去（注意对于这种时候要进行排序，其实结果对于顺序没有要求，进行排序以后方便进行下一步的操作）

#### 代码 ####

public List<List<Integer>> subsetsWithDup(int[] nums) { 
      List<List<Integer>> lists = new ArrayList<>();
            List<Integer> list = new ArrayList<>();
              Arrays.sort(nums);
            dfs(0,nums,list,lists);
            return  lists;
        }
        private  static  void dfs(int index,int [] nums,List<Integer> list,List<List<Integer>> lists){ 
    
            lists.add(new ArrayList<>(list));
            for(int i = index;i<nums.length;i++){ 
                if(i>index && nums[i]==nums[i-1])
                { 
                    continue;
                }
                list.add(nums[i]);
                dfs(i+1,nums,list,lists);
                list.remove(list.size()-1);
            }
        }

[46-]: https://leetcode-cn.com/problems/permutations/
[image-20200908165813521.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908165813521.png
[image-20200908170110181.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908170110181.png
[II]: https://leetcode-cn.com/problems/permutations-ii/
[image-20200908170911500.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908170911500.png
[39-]: https://leetcode-cn.com/problems/combination-sum/
[image-20200908141646833.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908141646833.png
[image-20200908143544738.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908143544738.png
[image-20200908150258736.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908150258736.png
[40-]: https://leetcode-cn.com/problems/combination-sum-ii/
[image-20200908160509705.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908160509705.png
[II 1]: https://leetcode-cn.com/problems/permutations-ii/solution/hui-su-suan-fa-python-dai-ma-java-dai-ma-by-liwe-2/
[77-]: https://leetcode-cn.com/problems/combinations/
[image-20200908171623606.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908171623606.png
[78-]: https://leetcode-cn.com/problems/subsets/
[image-20200908194002605.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908194002605.png
[90-_II]: https://leetcode-cn.com/problems/subsets-ii/
[image-20200908195641352.png]: https://gitee.com/maycopes/MyImages/raw/master//images/image-20200908195641352.png