回溯中等1 种解法

#78子集

返回不含重复元素数组的幂集。

#回溯#数组#子集

解题主线

子集题与组合题不同：搜索树上的每个节点都是一个合法答案，因此进入递归后立即复制路径。

下一层从 i + 1 开始，保证每个元素只选一次且不会生成顺序不同的重复子集。

解法 1：枚举搜索树节点

每次递归先保存当前路径，再依次选择 start 之后的元素向下搜索。

时间复杂度

O(n × 2^n)，共 2^n 个子集且复制长度最多为 n

空间复杂度

O(n)，不计输出

78. 子集 · 枚举搜索树节点

java

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);
        }
    }
}

每次递归先保存当前路径，再依次选择 start 之后的元素向下搜索。

两个旧文件仅在字段命名和 removeLast/remove(size - 1) 上不同，已去除机械重复。

边界与易错点

空集也是答案，空数组的结果应为包含一个空列表的列表。
start == nums.length 时仍需收集当前路径，额外的 start > length 判断没有实际作用。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

backtrack/Q078_backtrack_subsets.javabacktrack/Q078_subset.java