回溯中等1 种解法
#78子集
返回不含重复元素数组的幂集。
#回溯#数组#子集
原题
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3] 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：
输入：nums = [0] 输出：[[],[0]]
提示：
1 <= nums.length <= 10-10 <= nums[i] <= 10nums中的所有元素 互不相同
解题主线
- 子集题与组合题不同：搜索树上的每个节点都是一个合法答案，因此进入递归后立即复制路径。
- 下一层从 i + 1 开始，保证每个元素只选一次且不会生成顺序不同的重复子集。
解法 1：枚举搜索树节点
每次递归先保存当前路径，再依次选择 start 之后的元素向下搜索。
-
时间复杂度： O(n × 2^n)，共 2^n 个子集且复制长度最多为 n
-
空间复杂度： O(n)，不计输出
import java.util.ArrayList;
import java.util.List;
final class Solution {
public List<List<Integer>> subsets(int[] nums) {
// 搜索树的每个节点都代表一个合法子集，因此进入递归即收集路径。
// 下一层从所选下标的后一位开始，避免重复选择和排列型重复。
// 回溯返回前撤销末尾元素，恢复父层路径不变量。
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, new ArrayList<>(), result);
return result;
}
private void backtrack(int[] nums, int start,
List<Integer> path, List<List<Integer>> result) {
result.add(new ArrayList<>(path));
for (int i = start; i < nums.length; i++) {
path.add(nums[i]);
backtrack(nums, i + 1, path, result);
path.remove(path.size() - 1);
}
}
}实现提示
- 两个旧文件仅在字段命名和 removeLast/remove(size - 1) 上不同，已去除机械重复。
边界与易错点
- 空集也是答案，空数组的结果应为包含一个空列表的列表。
- start == nums.length 时仍需收集当前路径，额外的 start > length 判断没有实际作用。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q078_backtrack_subsets.javabacktrack/Q078_subset.java