LeetCode—78.子集(Subsets)——分析及代码(C++)

mac2024-03-30  34

LeetCode—78.子集[Subsets]——分析及代码[C++]

一、题目二、分析及代码1. 回溯法(1)思路(2)代码(3)结果 2. 层序遍历(1)思路(2)代码(3)结果 三、其他

一、题目

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

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

示例:

输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/subsets 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

二、分析及代码

1. 回溯法

(1)思路

依次遍历寻找各个长度的子集,针对单个长度的子集,采用回溯法求解。 通过每次回溯后只选取后部的数字,避免出现重复解。

(2)代码

class Solution { public: vector<vector<int>> ans; int nsize;//输入数组长度 vector<vector<int>> subsets(vector<int>& nums) { nsize = nums.size(); if (nsize == 0) return { {} }; vector<int> a;//单个答案子串 for (int i = 0; i < nsize + 1; i++)//遍历各个长度的子集 findSubset(nums, a, i, 0, 0); return ans; } //函数用于回溯寻找固定长度的子集,len所需长度,count当前长度,start当前可选取字符对应的最小下标(用于避免重复) void findSubset(vector<int> & nums, vector<int> & a, int len, int count, int start) { if (len == count) { ans.push_back(a); return; } for (int i = start; i < nsize; i++) { a.push_back(nums[i]); findSubset(nums, a, len, count + 1, i + 1); a.pop_back(); } } };

(3)结果

执行用时 :8 ms, 在所有 C++ 提交中击败了 89.17% 的用户; 内存消耗 :9.3 MB, 在所有 C++ 提交中击败了 33.71% 的用户。

2. 层序遍历

(1)思路

遍历所有数字,每个循环中依次复制当前解集中的所有元素并添加当前数字,扩充原解集。

(2)代码

class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { int nsize = nums.size(); vector<vector<int>> ans; ans.push_back({}); for (int i = 0; i < nsize; i++) { int rsize = ans.size(); for (int j = 0; j < rsize; j++) { vector<int> nres = ans[j];//复制解集中子串 nres.push_back(nums[i]);//添加当前数字 ans.push_back(nres);//加入解集 } } return ans; } };

(3)结果

执行用时 :4 ms, 在所有 C++ 提交中击败了 99.85% 的用户; 内存消耗 :9 MB, 在所有 C++ 提交中击败了 78.61% 的用户。

三、其他

暂无。

最新回复(0)