回溯算法中全排列是n叉树结构，需used数组标记已用元素并按位置填坑；子集是二叉树结构，靠start参数控制不重复选、每个中间状态即为子集。

回溯算法解决全排列和子集生成，关键在于区分“是否允许重复使用元素”和“是否关心顺序”。全排列要求每个元素只用一次、顺序敏感；子集则每个元素至多选一次、顺序无关，且天然包含空集。

全排列：逐层填坑 + 标记已用

对数组 [1, 2, 3] 生成所有排列，核心是模拟“填位置”的过程：

JavaStoryDevelop

你接手一个需求时，是不是经常这样："改一个小字段 → 结果把不相关的代码也改了"、"需求说得很模糊 → 做着做着发现跑偏了"、"数据库加个字段 → 上线才发现漏了数据兼容"、"做了个新功能 → 一个月后自己都忘了当时怎么设计的"、"写到一半被中断 → 再回来不知道从哪继续"；这个 Skill 就是专门解决这些问题的。 它会自动探测你的项目环境（JDK、Spring Boot、ORM、数据库、前端框架），记在

下载

• 每层递归对应一个位置（第0位、第1位、第2位）
• 用布尔数组 used[] 记录哪些数已被填入，避免重复选取
• 路径 path 存当前排列，长度达数组长度时加入结果
• 每次选一个未用数字，递归深入；返回后立刻 pop() 并重置 used[i]

子集生成：每个元素“选或不选” + 控制搜索范围

对数组 [1, 2, 3] 生成所有子集，本质是二叉决策树：

• 从索引 start 开始遍历，保证只往后选，避免 [1,2] 和 [2,1] 重复
• 进入递归前就将当前 path 加入结果——因每个中间状态本身就是一个合法子集
• 先选 nums[i]，递归处理 i+1 起的元素；再撤销，继续下一轮
• 不需要额外标记数组，靠 start 参数自然去重

两者的结构差异一目了然

全排列的递归树是**n叉树**：每层有多个可选分支，依赖 used 剪枝；子集的递归树是**二叉树**：每个元素只有“取/不取”两个分支，靠 start 控制方向。写代码时，前者循环内做选择→递归→撤销；后者先记录当前状态，再分两支递归——逻辑清晰，不易混淆。