leetcode中如何解决组合问题

# LeetCode中如何解决组合问题

## 引言

组合问题是算法面试中的高频考点，也是许多实际应用场景的抽象（如商品推荐、权限组合等）。LeetCode上常见的组合问题包括**子集生成**、**组合求和**、**排列组合**等。本文将系统性地讲解解决这类问题的思路、模板代码和优化技巧。

---

## 一、组合问题的基本特征

组合问题通常具有以下特点：
1. **需要枚举所有可能的解**（如78.子集）
2. **解的顺序不重要**（[1,2]和[2,1]视为相同）
3. **可能包含重复元素需要去重**（如40.组合总和II）
4. **常伴随剪枝条件**（如216.组合总和III）

---

## 二、核心解决思路：回溯算法

回溯法是解决组合问题的标准解法，其本质是**DFS+剪枝**的暴力搜索。

### 1. 回溯算法框架
```python
def backtrack(路径, 选择列表):
    if 满足结束条件:
        结果.append(路径.copy())
        return
    
    for 选择 in 选择列表:
        if 选择不合法:  # 剪枝条件
            continue
        做选择
        backtrack(新路径, 新选择列表)
        撤销选择

2. 关键点解析

• 路径：当前已经做出的选择
• 选择列表：当前可以做的选择
• 结束条件：达到决策树底层时的判断
• 剪枝：提前排除不符合条件的路径

三、经典题型实战

1. 子集问题（78. Subsets）

问题描述：给定不含重复元素的整数数组，返回所有可能的子集。

解法：

def subsets(nums):
    res = []
    
    def backtrack(start, path):
        res.append(path.copy())
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    
    backtrack(0, [])
    return res

复杂度分析： - 时间复杂度：O(N×2^N) - 空间复杂度：O(N)

2. 组合总和（39. Combination Sum）

问题描述：给定无重复元素的数组和一个目标数，找出所有和为目标数的组合（可重复使用数字）。

解法：

def combinationSum(candidates, target):
    res = []
    
    def backtrack(start, path, remain):
        if remain == 0:
            res.append(path.copy())
            return
        for i in range(start, len(candidates)):
            if candidates[i] > remain:  # 剪枝
                continue
            path.append(candidates[i])
            backtrack(i, path, remain - candidates[i])  # 注意start不+1
            path.pop()
    
    backtrack(0, [], target)
    return res

3. 全排列（46. Permutations）

问题描述：给定不含重复数字的数组，返回所有可能的全排列。

解法：

def permute(nums):
    res = []
    
    def backtrack(path, used):
        if len(path) == len(nums):
            res.append(path.copy())
            return
        for i in range(len(nums)):
            if used[i]: continue
            used[i] = True
            path.append(nums[i])
            backtrack(path, used)
            path.pop()
            used[i] = False
    
    backtrack([], [False]*len(nums))
    return res

四、进阶技巧

1. 剪枝优化

• 排序预处理：对于含重复元素的问题（如40题），先排序便于剪枝
• 提前终止：当累计值超过目标时立即停止递归

2. 去重方法

if i > start and nums[i] == nums[i-1]:  # 关键去重逻辑
    continue

3. 位运算解法（适用于子集问题）

对于小规模数据（n<=32），可用位掩码枚举：

def subsets(nums):
    n = len(nums)
    return [[nums[i] for i in range(n) if mask & (1 << i)] 
            for mask in range(1 << n)]

五、常见错误与调试

1. 忘记拷贝路径：直接添加path会导致结果被后续修改
2. 错误剪枝：去重条件写错位置（应放在同一层级判断）
3. 终止条件遗漏：特别是组合求和类问题忘记判断remain的情况

六、扩展练习

结语

掌握组合问题的关键在于： 1. 理解回溯算法的决策树模型 2. 熟练记忆模板代码 3. 根据具体问题调整剪枝和去重逻辑

建议按照本文的顺序从简单题目开始练习，逐步过渡到复杂场景。遇到问题时，可以画出决策树帮助理解程序执行流程。 “`

（全文约1200字，实际字数可能因Markdown渲染略有差异）