02 子集问题
# LeetCode刷题笔记 回溯算法
# 78 子集 (opens new window)
给你一个整数数组 nums
,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入:nums = [1,2,3] 输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
解析:
class Solution {
public:
void bt(vector<int>& nums, int start, vector<int>& track, vector<vector<int>>& ans){
ans.push_back(track);
for(int i=start;i<nums.size();++i){
track.push_back(nums[i]);
bt(nums,i+1,track,ans);
track.pop_back();
}
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> track;
vector<vector<int>> ans;
bt(nums,0,track,ans);
return ans;
}
};
# 90 子集 II (opens new window)
给你一个整数数组 nums ,其中可能包含重复元素,请你返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。返回的解集中,子集可以按 任意顺序 排列。
输入:nums = [1,2,2] 输出:[[],[1],[1,2],[1,2,2],[2],[2,2]]
解析:
class Solution {
public:
void bt(vector<int>& nums, int start, vector<int>& track, vector<vector<int>>& ans, vector<bool>& visited){
ans.push_back(track);
for(int i=start;i<nums.size();++i){
if(i>start&&nums[i]==nums[i-1]&&!visited[i-1]){
continue;
}
track.push_back(nums[i]);
visited[i] = true;
bt(nums,i+1,track,ans,visited);
visited[i] = false;
track.pop_back();
}
return;
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> track;
vector<vector<int>> ans;
// 重复元素判断是否使用过,同一子集中可以重复使用,不同子集中不行,不然出现重复子集
vector<bool> visited(nums.size(),false);
// 去重要排序,不然不容易识别重复元素
sort(nums.begin(),nums.end());
bt(nums,0,track,ans,visited);
return ans;
}
};
上次更新: 2023/11/19, 12:55:48