leetcode:77.组合

来源：力扣（LeetCode）

链接: 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 <= k <= n

• 递归: 将结果划分为两部分，每次取前面的1个元素，后面的元素结果使用递归生成，再遍历后面的元素结果，将前面的1个元素拼接进去，作为最终结果；前面一个元素的个数为(n-k+1), 因为本题不考虑顺序。

• 回溯法：每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。回溯三部曲：

  • 递归函数的返回值以及参数：每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠curIndex
  • 回溯函数终止条件:搜索的结果满足长度后，加入到ans中；剪枝，不满足后续递归结果后停止递归；
  • 单层搜索的过程：是否加入该节点，加入该节点后继续回溯，不加入该节点后继续回溯；

python实现

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        def helper(array: List[int], k: int) -> List[List[int]]:
            if k == 1:
                return [[i] for i in array]
            else:
                res = []
                for i in range(len(array)-k+1):  # 开头有多少种数字
                    right_parts = helper(array[i+1:], k-1)
                    for part in right_parts:
                        res.append([array[i]] + part)
                return res
        return helper(list(range(1, n+1)), k)

c++实现

class Solution {
public:
    vector> helper(vector array, int k){
        if (k == 1) {
            vector> res;
            for(int v: array) {
                res.push_back({v});
            }
            return res;
        }
        else {
            vector> res;
            int tmp_size = array.size() - k + 1;
            for (int i=0; i
                vector tmp_array(array.begin()+i+1, array.end());
                vector> right_parts = helper(tmp_array, k-1);
                for(auto part: right_parts){
                    part.push_back(array[i]);
                    res.push_back(part);
                }
            }
            return res;
        }
    }

    vector> combine(int n, int k) {
        vector array;
        for(int i=1; i
            array.push_back(i);
        }
        return helper(array, k);
    }
};

复杂度分析

• 时间复杂度： O ( N 2 ) O(N^2) O(N2)
• 空间复杂度： O ( N ) O(N) O(N)

python实现

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        ans = []
        tmp = []

        def helper(cur, n, k):
            if len(tmp) + n-cur+1 < k:
                return
            if len(tmp) == k:
                ans.append(tmp[:])   # 数组浅拷贝 深拷贝 需要加[:]
                return
            if cur > n:
                return
            
            tmp.append(cur) # 考虑该元素 
            helper(cur+1, n, k)
            tmp.pop() # 回溯
            helper(cur+1, n, k)  # 不考虑该元素
        
        helper(1, n, k)
        return ans

c++实现

class Solution {
public:
    vector tmp;
    vector> ans;

    void dfs(int cur, int n, int k) {
        if (tmp.size() + n-cur+1 < k)
            return;
        
        if (tmp.size() == k) {
            ans.push_back(tmp);
            return;
        }

        tmp.push_back(cur);
        dfs(cur+1, n, k);
        tmp.pop_back();
        dfs(cur+1, n, k);
    }

    vector> combine(int n, int k) {
        dfs(1, n, k);
        return ans;
    }
};

复杂度分析

• 时间复杂度： O ( ( n k ) × k ) O({n choose k} times k) O((kn​)×k)
• 空间复杂度： O ( N ) O(N) O(N)

• https://leetcode.cn/problems/combinations/solution/zu-he-by-leetcode-solution/
• https://leetcode.cn/problems/combinations/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-hui-s-0uql/