77. 组合 - 递归

缺乏、安全感 2023-02-08 12:49 23阅读 0赞

> 熟悉我的读者朋友都知道，我是面向思维做题，做题是为了保持时间复杂度、空间复杂度的敏感，顺便锻炼一下脑筋，把思维用代码表达出来。
> 
> 题目的解法不止一种，我会记住一两种。我的选择标准是：思路简单，代码清晰

[题目链接][Link 1]

给定两个整数 n 和 k，返回范围 \[1, n\] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

输入：n = 4, k = 2  
输出：

[
      [2,4],
      [3,4],
      [2,3],
      [1,2],
      [1,3],
      [1,4],
    ]

示例 2：

输入：n = 1, k = 1
    输出：[[1]]

提示：

1 <= n <= 20  
1 <= k <= n

## 题目分析 ##

这道题用递归来完成。  
关于递归，建议看看极客时间，覃超老师用电影《盗梦空间》解释递归的框架：

public void dfs( param1, param2 ...) {
        
    	第一部分：递归终止条件
    	第二部分：做本层工作
    	第三部分：潜入下一层
    	第四部分：清理本层
    }

这一道题的递归解法也差不多。

class Solution {
        
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        
        public List<List<Integer>> combine(int n, int k) {
        
            dfs(1,n,k);
            return ans;
        }
    
        public void dfs(int cur, int n, int k  ) {
        
    		// 第一部分：递归终止条件
            if (temp.size() == k ) {
        
                ans.add(new ArrayList<>(temp));
                return ;
            }
            if (cur  == n + 1) {
        
                 return;
            }
    
           // 第二部分：做本层工作
            temp.add(cur);  // 选择当前元素
            
            // 第三部分：潜入下一层
            dfs(cur+1, n, k);
            temp.remove(temp.size()-1);  // 不选当前元素
            // 再次潜入下一层
            dfs(cur+1, n ,k);
            
    		// 第四部分：清理本层
    		// ...无
        }
    
    }

这样做其实已经通过了。

第一个下潜结束，回到本层，然后从不选当前元素，到再次潜入下一层，这个过程称为 ***回溯***

递归的过程是立体的

把递归的过程看成从1开始，选1和不选1，得到2个子树

在第二层，选2和不选2 ，又分别得到2个子树

第三层，选3和不选3，又分别得到2个子树

第四层，选4和不选4，又分别得到2个子树

对于一些明显不可能构成结果的子树，可以提前结束下潜，这种操作称之为 ***剪枝***

剪枝的过程如下：

如果当前 temp 的大小为 s，未确定状态的区间 \[cur, n\] 的长度为 t，如果 s + t<k，那么即使 t 个都被选中，也不可能构造出一个长度为 k 的序列，故这种情况就没有必要继续向下递归，即我们可以在每次递归开始的时候做一次这样的判断：

if (temp.size() + (n - cur + 1) < k) {
        
        return;
    }

最终代码

class Solution {
        
    
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        
        public List<List<Integer>> combine(int n, int k) {
        
            dfs(1,n,k);
            return ans;
        }
    
        public void dfs(int cur, int n, int k  ) {
        
    		// 第一部分：递归终止条件
            if (temp.size() == k ) {
        
                ans.add(new ArrayList<>(temp));
                return ;
            }
            if (cur  == n + 1) {
        
                 return;
            }
    		// 根据题目条件，做一个小小的剪枝
    		if (temp.size() + (n - cur + 1) < k) {
        
                return;
            }        
    
           // 第二部分：做本层工作
            temp.add(cur);  // 选择当前元素
            
            // 第三部分：潜入下一层
            dfs(cur+1, n, k);
            temp.remove(temp.size()-1);  // 不选当前元素
            // 再次潜入下一层
            dfs(cur+1, n ,k);
            
    		// 第四部分：清理本层
    		// ...无
        }
    
    }

剪枝之后，减少了递归次数，优化了耗时。

TODO： 补充极客时间的链接，二叉树的图。补充提交记录的截图。

[Link 1]: https://leetcode-cn.com/problems/combinations