# 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(新路径, 新选择列表) 撤销选择 问题描述：给定不含重复元素的整数数组，返回所有可能的子集。
解法：
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)
问题描述：给定无重复元素的数组和一个目标数，找出所有和为目标数的组合（可重复使用数字）。
解法：
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 问题描述：给定不含重复数字的数组，返回所有可能的全排列。
解法：
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 if i > start and nums[i] == nums[i-1]: # 关键去重逻辑 continue 对于小规模数据（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)] | 题目编号 | 名称 | 难度 | 核心考点 |
|---|---|---|---|
| 77 | 组合 | Medium | 基础回溯 |
| 90 | 子集II | Medium | 含重复元素 |
| 216 | 组合总和III | Medium | 剪枝优化 |
| 131 | 分割回文串 | Medium | 组合变种 |
掌握组合问题的关键在于： 1. 理解回溯算法的决策树模型 2. 熟练记忆模板代码 3. 根据具体问题调整剪枝和去重逻辑
建议按照本文的顺序从简单题目开始练习，逐步过渡到复杂场景。遇到问题时，可以画出决策树帮助理解程序执行流程。 “`
（全文约1200字，实际字数可能因Markdown渲染略有差异）
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
