【算法题解】29. 组合的递归解法

青旅半醒 2024-03-22 18:54 66阅读 0赞

> 这是一道 **中等难度** 的题  
>   
> https://leetcode.cn/problems/combinations/

### 题目 ###

给定两个整数 `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 <= n <= 20 1<=n<=20
 *   1 < = k < = n 1 <= k <= n 1<=k<=n

### 题解 ###

这道题的解题思路和 [子集][Link 1] 是一样的，每个数都有 **选** 和 **不选** 两个选项。

但这个题目限定了组合（也就是子集）的长度为 `k` ，所以需要在最后判断一下只有子集 `subSet` 的大小为 `k` 的时候才能计入答案。

另外这题有个可以优化的点：  
如果**当前子集 `subSet` 的大小** 加上 **剩余的所有数字** 都还小于 `k` , 那么这个分支就可以剪掉，因为即使走到最后一步也无法满足条件。

##### Java 代码实现 #####

class Solution {
        
        private List<Integer> subSet = new ArrayList<>();
        private List<List<Integer>> ans = new ArrayList<>();
        
        public List<List<Integer>> combine(int n, int k) {
        
            recursion(1, n, k);
            return ans;
        }
    
        private void recursion(int i, int n, int k){
        
    
            // 当已经选够了 k 个数的时候，后面就不需要计算了
            if(subSet.size() == k){
        
                ans.add(new ArrayList(subSet));
                return;
            }
    
            //当剩下的数全部选上都不够k个的时候，直接返回。
            if(subSet.size() + (n - i + 1) < k){
        
                return;
            }
    
            // 不选
            recursion(i + 1, n, k);
    
    
            // 选
            subSet.add(i);
            recursion(i + 1, n, k);
            subSet.remove(subSet.size() - 1);
        }
    }

##### Go 代码实现 #####

var ans [][]int
    var subSet []int
    
    func combine(n int, k int) [][]int {
        
        subSet = []int{
        }
        ans = [][]int{
        }
    
        recursion(1, n, k)
    
        return ans
    
    }
    
    func recursion(i int, n int, k int) {
        
        if k == len(subSet) {
        
            temp := make([]int, len(subSet))
            copy(temp, subSet)
            ans = append(ans, temp)
            return
        }
    
        if (len(subSet) + (n - i + 1)) < k {
        
            return
        }
    
        // 不选
        recursion(i + 1, n, k)
    
        // 选
        subSet = append(subSet, i)
        recursion(i + 1, n, k)
        subSet = subSet[:len(subSet) - 1]
    }

[Link 1]: https://mp.weixin.qq.com/s?__biz=MzU1OTYwMjk1OQ==&mid=2247487399&idx=1&sn=38e862407d9c18c34b830586d556e376&chksm=fc1583c7cb620ad143d51c846e002278b3205115daa6e1b649d3b5961f3f3a7aaca929c522e1#rd