93.復原IP地址
先跳過
78.子集
給你一個整數(shù)數(shù)組 nums 良风，數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集（冪集）慎颗。
解集 不能 包含重復的子集悲酷。你可以按 任意順序 返回解集。
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backTrack(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]);
backTrack(nums, i+1);
path.pop_back();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backTrack(nums, 0);
return result;
}
};
90. 子集 II
給你一個整數(shù)數(shù)組 nums 疮胖，其中可能包含重復元素环戈，請你返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復的子集澎灸。返回的解集中院塞，子集可以按 任意順序 排列。
輸入：nums = [1,2,2]
輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
class Solution {
private:
vector<int> path;
set<vector<int>> result;
void backTrack(vector<int>& nums, int startIndex, vector<bool> used) {
//if (path.size() == 0) {
result.insert(path);
//}
if (startIndex >= nums.size()) {
return;
}
for (int i = startIndex; i < nums.size();i++) {
if (startIndex > 0 && nums[i-1] == nums[i] && used[i-1] == false) {
continue;
}
used[i] = true;
path.emplace_back(nums[i]);
backTrack(nums, i+1, used);
path.pop_back();
used[i] = false;
}
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(),nums.end());
vector<bool> used(nums.size(), false);
backTrack(nums, 0, used);
vector<vector<int>> finalResult(result.begin(), result.end());
return finalResult;
}
};
