浙江英文网站建设,wordpress主题位置,网上推广哪个平台好,t想学网站建设78. 子集 - 力扣#xff08;LeetCode#xff09;
题目描述
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。 样例输入
示例 1#xff1a;…78. 子集 - 力扣LeetCode
题目描述
给你一个整数数组 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 中的所有元素 互不相同
题解
使用回溯算法回溯的本质在于使用for循环控制每层遍历使用递归控制深度的树枝遍历 代码
解1
class Solution {
private:vectorint path;vectorvectorint res;
public:void backing(vectorint nums,int startIndex){// if(startIndexnums.size())// return ;for(int istartIndex;inums.size();i){path.push_back(nums[i]);//遍历路径节点res.push_back(path);//收集每一个路径上的结果backing(nums,i1);//深层遍历path.pop_back();//回溯}}vectorvectorint subsets(vectorint nums) {res.push_back({});backing(nums,0);return res;}
};
解2
class Solution {
private:vectorint path;vectorvectorint res;
public:void backing(vectorint nums,int startIndex){res.push_back(path);// if(startIndexnums.size())// return ;for(int istartIndex;inums.size();i){path.push_back(nums[i]);backing(nums,i1);path.pop_back();}}vectorvectorint subsets(vectorint nums) {backing(nums,0);return res;}
}; 解3 另解不使用回溯使用二进制表示nums每个元素中的状态如nums[1,2,3]每个元素都有取或者不取两种状态如果0表示不取该元素1表示取该元素则所有可取的情况如下图所示 class Solution {
private:vectorvectorint res;
public:vectorint getSubset(vectorint nums,int temp){int index 0;vectorint path;while (temp) {if (temp 1)//取出每一位的状态如果当前比特位为1就收集该元素path.push_back(nums[index]);index;temp 1;//右移取下一个比特位}return path;}vectorvectorint subsets(vectorint nums) {int n nums.size();for (int i 0; i (1 n); i) { //1n等于pow(2,n)vectorint pathgetSubset(nums,i);res.push_back(path);}return res;}
};
