leetcode78. 子集

Bea ·

更新时间:2024-09-21

· 684 次阅读

题目大意

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

解题思路 方法一：

解题思路同leetcode77.组合，采用回溯法。唯一不同的点在于，题目77中，只有当curNums的长度等于给定长度k时，才将其加入最终结果。本题中，对于任意一个curNums，不需要判断长度，直接放入最终结果中即可。

class Solution {
public:
    vector<vector> subsets(vector& nums) {
        if (nums.empty())
        	return {};
        vector<vector> res;
        vector curNums;
        dfs(res, nums, curNums, 0);
        return res;
    }
    void dfs(vector<vector> & res, vector & nums, vector & curNums, int index){
    	res.push_back(curNums);
    	if (index == nums.size())
    		return ;
    	for(int i = index; i < nums.size(); ++i){
    		curNums.push_back(nums[i]);
    		dfs(res, nums, curNums, i + 1);
    		curNums.pop_back();
    	}
    }
};

方法二：

最终的返回数组设为res。假设当前遍历到位置i，则0~i-1范围内的子集都已经在res中了。因此，只要将res数组中的每一个子集复制一份，并在每个复制的子集中加入当前元素nums[i],就能得到0 ~i范围内的全部子集。

class Solution {
public:
    vector<vector> subsets(vector& nums) {
        if (nums.empty())
        	return ;
        vector<vector> res, tmp;
        res.push_back({});
        vector curNums;
        for (int i = 0; i < nums.size(); ++i){
        	tmp = res;
        	for (int j = 0; j < tmp.size(); ++j){
        		curNums = tmp[j];
        		curNums.push_back(nums[i]);
        		res.push_back(curNums);
        	}
        }
        return res;
    }
};

作者：大腿壮

leetcode 子集

1024 个赞