组合问题（Combinations）
📌 定义
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
示例:
输入: n = 4, k = 2
输出:
[
[1,2],
[1,3],
[1,4],
[2,3],
[2,4],
[3,4]
]
输入: n = 1, k = 1
输出: [[1]]
核心思路
使用回溯算法，与全排列不同：
- 组合不考虑顺序：[1,2] 和 [2,1] 是同一个组合
- 使用start_index避免重复：只选择当前位置之后的元素
决策树示例 n=4, k=2:
[]
/ | | \
[1] [2] [3] [4]
/ | \ | \ |
[1,2][1,3][1,4][2,3][2,4][3,4]
只向右展开，避免重复
复杂度分析
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|---|---|---|
| 回溯法 | O(C(n,k) × k) | O(k) | C(n,k)种组合 |
| 迭代法 | O(C(n,k) × k) | O(C(n,k) × k) | 需要存储所有结果 |
| 二进制枚举 | O(2^n × k) | O(k) | 适用于小n |
Go 代码
Go 实现
package main
import (
"fmt"
"sort"
)
// 基本组合
func combine(n int, k int) [][]int {
result := [][]int{}
path := []int{}
var backtrack func(start int)
backtrack = func(start int) {
// 终止条件
if len(path) == k {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
return
}
// 剪枝优化
for i := start; i <= n-(k-len(path))+1; i++ {
path = append(path, i)
backtrack(i + 1)
path = path[:len(path)-1]
}
}
backtrack(1)
return result
}
// 组合总和
func combinationSum(candidates []int, target int) [][]int {
result := [][]int{}
path := []int{}
sort.Ints(candidates)
var backtrack func(start, currentSum int)
backtrack = func(start, currentSum int) {
if currentSum == target {
temp := make([]int, len(path))
copy(temp, path)
result = append(result, temp)
return
}
if currentSum > target {
return
}
for i := start; i < len(candidates); i++ {
if currentSum+candidates[i] > target {
break
}
path = append(path, candidates[i])
backtrack(i, currentSum+candidates[i])
path = path[:len(path)-1]
}
}
backtrack(0, 0)
return result
}
func main() {
// 测试基本组合
result := combine(4, 2)
fmt.Println("组合结果:")
for _, comb := range result {
fmt.Println(comb)
}
}思路展开
组合 vs 排列
排列：[1,2] 和 [2,1] 是不同的
组合：[1,2] 和 [2,1] 是相同的
避免重复的方法：
- 使用start_index，只向后选择
- 排列需要visited数组，组合不需要
示例 n=3, k=2:
排列会产生: [1,2], [1,3], [2,1], [2,3], [3,1], [3,2]
组合只产生: [1,2], [1,3], [2,3]
剪枝优化详解
n=4, k=2，需要选2个数
在i=3时：
- path = [3]
- 还需要选 k - len(path) = 2 - 1 = 1 个数
- 剩余元素：[4]，共 n - i = 4 - 3 = 1 个
- 1 >= 1 ✓ 可以继续
在i=4时：
- path = []
- 还需要选 k - len(path) = 2 - 0 = 2 个数
- 剩余元素：[]，共 n - i = 4 - 4 = 0 个
- 0 < 2 ✗ 无法继续，剪枝
剪枝条件：
需要：n - i + 1 >= k - len(path)
即：i <= n - (k - len(path)) + 1
组合总和去重详解
candidates = [1, 1, 2], target = 3
排序后：[1, 1, 2]
树形结构:
[]
/ | \
[1] [1]× [2]
/ \ / \ |
[1,1][1,2] [1,1]×[1,2]× [2,1]
| | | |
[1,1,1][1,1,2] ... ...
× 标记的是被剪枝的分支
去重条件（树层去重）:
if i > start and candidates[i] == candidates[i-1]:
continue
解释:
- i > start: 不是当前层的第一个元素
- candidates[i] == candidates[i-1]: 与前一个相同
→ 在同一层会产生重复，需要剪枝
经典题目
LeetCode 问题
- 组合 - LeetCode 77
- 组合总和 - LeetCode 39
- 组合总和 II - LeetCode 40
- 组合总和 III - LeetCode 216
- 电话号码的字母组合 - LeetCode 17
- 因子的组合 - LeetCode 254
扩展问题
- 大小为k且和为s的所有组合
- 组合的字典序第k个
⚖️ 优缺点
优点
- ✅ 避免重复：使用start_index自然去重
- ✅ 易于剪枝：多种剪枝条件
- ✅ 空间高效：不需要visited数组
缺点
- ❌ 指数时间复杂度：C(n,k)可能很大
- ❌ 不适合大规模：n > 30时性能差