[Leetcode][第77题][JAVA][组合][回溯]

﹏ヽ暗。殇╰゛Y 2022-12-04 12:58 152阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

###### 1. 回溯 ######

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

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

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

###### 2. 回溯优化 ######

分析搜索起点的上界进行剪枝  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]

class Solution { 
    
        List<List<Integer>> lists = new ArrayList<>();
    
        public List<List<Integer>> combine(int n, int k) { 
            List<Integer> list = new ArrayList<>();
            backTrace(list, n, k, 0);
            return lists;
        }
        
         private void backTrace(List<Integer>list, int n, int k, int depth){ 
             if(depth>k){ 
                 return ;
             }
            if(depth == k){ 
                lists.add(new ArrayList<>(list));
                return;
            }
    // 只有这里 i <= n - (k - path.size()) + 1 与参考代码 1 不同
            for(int i = 1;i <= n - (k - path.size()) + 1  ; i++){ 
                list.add(i);
                backTrace(list, n, k, depth+1);
                list.remove(list.size()-1);
            }
    
        }
    }

#### 【总结】 ####

###### 1. 回溯法解决组合问题。和排列问题不同的是，在组合问题中元素的顺序不考虑，只需要从当前位置向后寻找。排列问题每次都需要从头寻找，需要用visited数组记录访问过的元素。 ######

###### 2.相关题目 ######

[\[Leedcode\]\[JAVA\]\[第46题\]\[全排列\]\[回溯算法\]][Leedcode_JAVA_46]  
[\[Leetcode\]\[第81题\]\[JAVA\]\[N皇后问题\]\[回溯算法\]][Leetcode_81_JAVA_N]  
[\[Leetcode\]\[第60题\]\[JAVA\]\[第k个排列\]\[回溯\]\[DFS\]\[剪枝\]][Leetcode_60_JAVA_k_DFS]

转载：https://leetcode-cn.com/problems/combinations/solution/hui-su-suan-fa-jian-zhi-python-dai-ma-java-dai-ma-/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/bb4dddf223954f099060d342bf7bff88.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/1d699a4a180b4050bd3125f2ca13e7b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/b98f3c6fc5184e42bb3766dc169f660b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/693e33ce585b4844a0d640f50315aff5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/5bfb10d7e4554ea7aecee2b0c636d25e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/320f55adf01041528f8a1c626b988de8.png
[Leedcode_JAVA_46]: https://blog.csdn.net/dadongwudi/article/details/105760561
[Leetcode_81_JAVA_N]: https://blog.csdn.net/dadongwudi/article/details/108379661
[Leetcode_60_JAVA_k_DFS]: https://blog.csdn.net/dadongwudi/article/details/108419966