排列组合

📌 核心概念

• 排列（Permutation）：从n个元素中取m个进行排列，顺序重要
• 组合（Combination）：从n个元素中取m个，顺序无关

这一篇解决什么

这篇先讲“排列数、组合数、杨辉三角、康托展开”的基础框架。 如果题目进一步要求：

• 大组合数取模：看 组合数取模与Lucas定理
• 合法括号 / BST 结构数：看 卡特兰数

💻 基本公式

排列数

P(n, m) = n! / (n-m)!
        = n × (n-1) × ... × (n-m+1)

组合数

C(n, m) = n! / (m! × (n-m)!)
        = P(n, m) / m!

💻 算法实现

🎯 经典应用

💡 组合数性质

1. 对称性

C(n, m) = C(n, n-m)

2. 递推公式（杨辉三角）

C(n, m) = C(n-1, m-1) + C(n-1, m)

3. 求和公式

C(n, 0) + C(n, 1) + ... + C(n, n) = 2^n

4. 范德蒙德恒等式

C(m+n, k) = Σ C(m, i) * C(n, k-i)

🎯 优化技巧

📊 复杂度分析

方法	时间复杂度	空间复杂度	适用场景
直接计算	O(m)	O(1)	单次查询
DP	O(n*k)	O(k)	多次查询
预处理	O(n²)	O(n²)	大量查询

Go 代码

// 计算组合数
func combination(n, m int) int {
    if m > n || m < 0 {
        return 0
    }
 
    if m > n-m {
        m = n - m
    }
 
    result := 1
    for i := 0; i < m; i++ {
        result = result * (n - i) / (i + 1)
    }
 
    return result
}
 
// 杨辉三角
func generate(numRows int) [][]int {
    triangle := make([][]int, numRows)
 
    for i := 0; i < numRows; i++ {
        triangle[i] = make([]int, i+1)
        triangle[i][0], triangle[i][i] = 1, 1
 
        for j := 1; j < i; j++ {
            triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j]
        }
    }
 
    return triangle
}

🎯 经典题目

题目	LeetCode	关键点
杨辉三角	118	递推公式
杨辉三角II	119	空间优化
第k个排列	60	康托展开
电话号码的字母组合	17	回溯
组合总和	39	回溯+剪枝

🔗 相关笔记

• 组合数取模与Lucas定理
• 卡特兰数

---

返回：数学算法