当前位置：首页 > article >正文

LeetCode 78.子集

article 2025/3/19 10:29:21

题目描述

给你一个整数数组 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] <= 10
nums 中的所有元素 互不相同

思路

该问题不是排序问题，for就要从startIndex开始，而不是从0开始。求排列问题的时候，才要从0开始，因为集合是有序的。

本题题意就是要求树的所有节点，所以在遍历这棵树的时候把所有节点都记录就行。

回溯法三部曲：

确定递归函数的参数和返回值。全局变量数组path为子集收集元素，二维数组result存放子集组合。递归参数需要传入原字符串和startIndex，startIndex表示下一轮递归遍历的起始位置。返回值为空。
确定终止条件。如果起始位置已经大于s的大小，说明已经遍历完成。
确定单层递归的逻辑。求解子集问题，不需要任何剪枝，因为子集就是要遍历整棵树。

代码

C++版：

class Solution {
public:
    // 回溯法，子集问题
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums,int startIndex){
        result.push_back(path); // 收集子集，包括空集
        // 终止条件
        if(startIndex >= nums.size()){
            return ;
        }
        for(int i=startIndex;i<nums.size();i++){
            path.push_back(nums[i]);
            backtracking(nums,i+1);
            path.pop_back();
        }
    }
    vector<vector<int>> subsets(vector<int>& nums) {
        backtracking(nums,0);
        return result;
    }
};

Python版：

class Solution:
    # 回溯法
    def backtracking(self, nums, startIndex, path, result):
        result.append(path[:])  # 收集子集，包括空集
        if startIndex >= len(nums):  # 终止条件
            return
        for i in range(startIndex, len(nums)):
            path.append(nums[i])
            self.backtracking(nums, i + 1, path, result)
            path.pop()
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        self.backtracking(nums, 0, path, result)
        return result