目錄
前言：
78. 子集
題目描述：
輸入輸出描述：
思路和想法：
90. 子集 II
題目描述：
輸入輸出描述：
思路和想法：
491. 遞增子序列
題目描述：
輸入輸出描述：
思路和想法：
前言：
如果把 子集問(wèn)題、組合問(wèn)題、分割問(wèn)題都抽象為一棵樹的話，那么組合問(wèn)題和分割問(wèn)題都是收集樹的葉子節(jié)點(diǎn)，而子集問(wèn)題是找樹的所有節(jié)點(diǎn)！
子集是無(wú)序的，取過(guò)的元素不會(huì)重復(fù)取，寫回溯算法的時(shí)候，for就要從Index開始。
之后討論的問(wèn)題，分為兩種：
- 集合里無(wú)重復(fù)元素
- 集合里有重復(fù)元素，求取的子集需要進(jìn)行去重（可排序）
- 集合中找遞增子集（不可排序）
78. 子集
題目描述：
給你一個(gè)整數(shù)數(shù)組 nums ，數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集。
輸入輸出描述：
示例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] <= 10
- nums 中的所有元素 互不相同
思路和想法：
這一道題是模板題，可以從這道題感受子集問(wèn)題解法與之前的不同。
#include <bits/stdc++.h>
using namespace std;
/*
* 作者：希希霧里
* 78. 子集
* */
vector<vector<int>> result;
vector<int> path;
/*
* 函數(shù)： backtracing（）
* 輸入?yún)?shù)： s：輸入的字符串 index：數(shù)組元素下標(biāo)
* */
void backtracing(vector<int> &nums,int Index){
result.push_back(path);
//回溯過(guò)程
for (int i = Index; i < nums.size(); ++i) {
path.push_back(nums[i]);
backtracing(nums,i + 1);
path.pop_back();
}
};
int main() {
result.clear();
path.clear();
int num;
vector<int> nums;
while(cin>>num){
nums.push_back(num);
if(getchar() == '\n'){
break;
}
}
backtracing(nums,0);
cout << "[";
for (int i = 0; i < result.size(); ++i) {
cout << "[";
for (int j = 0; j < result[i].size(); ++j) {
cout<< result[i][j];
if(j != result[i].size() - 1) cout << ",";
}
cout << "]";
if(i != result.size() - 1) {cout << ",";}
}
cout << "]";
return 0;
}
/* 測(cè)試樣例
1 2 3
0
*
* */90. 子集 II
題目描述：
給你一個(gè)整數(shù)數(shù)組 nums ，其中可能包含重復(fù)元素，請(qǐng)你返回該數(shù)組所有可能的子集（冪集）。
解集 不能 包含重復(fù)的子集。返回的解集中，子集可以按 任意順序 排列。
輸入輸出描述：
示例1：
輸入：nums = [1,2,2] 輸出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例2：
輸入：nums = [0] 輸出：[[],[0]]
提示：
- 1 <= nums.length <= 10
- -10 <= nums[i] <= 10
思路和想法：
這道題目和上一道題之間的區(qū)別：集合里有了重復(fù)元素，而且求取的子集要進(jìn)行去重。
所以在上一道題的基礎(chǔ)上，引入樹層去重，這道題目可以參考回溯算法中組合問(wèn)題里的40.組合總和II。
#include <bits/stdc++.h>
using namespace std;
/*
* 作者：希希霧里
* 90. 子集II
* */
vector<vector<int>> result;
vector<int> path;
/*
* 函數(shù)： backtracing（）
* 輸入?yún)?shù)： s：輸入的字符串 index：數(shù)組元素下標(biāo) used:使用過(guò)的標(biāo)志
* */
void backtracing(vector<int> &nums,int Index, vector<bool> used){
result.push_back(path);
//回溯過(guò)程
for (int i = Index; i < nums.size(); ++i) {
// used[i - 1] == true，說(shuō)明同一樹枝nums[i - 1]使用過(guò)
// used[i - 1] == false，說(shuō)明同一樹層nums[i - 1]使用過(guò)
// 這里注意樹層和樹枝的區(qū)別，這里我們是對(duì)樹層進(jìn)行跳過(guò)。
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracing(nums,i + 1,used);
used[i] = false;
path.pop_back();
}
};
int main() {
result.clear();
path.clear();
int num;
vector<int> nums;
while(cin>>num){
nums.push_back(num);
if(getchar() == '\n'){
break;
}
}
vector<bool> used(nums.size(), false);
sort(nums.begin(),nums.end());
backtracing(nums,0,used);
//輸出模式
cout << "[";
for (int i = 0; i < result.size(); ++i) {
cout << "[";
for (int j = 0; j < result[i].size(); ++j) {
cout<< result[i][j];
if(j != result[i].size() - 1) cout << ",";
}
cout << "]";
if(i != result.size() - 1) {cout << ",";}
}
cout << "]";
return 0;
}
/* 測(cè)試樣例
1 2 2
0
*
* */491. 遞增子序列
題目描述：
給你一個(gè)整數(shù)數(shù)組 nums ，找出并返回所有該數(shù)組中不同的遞增子序列，遞增子序列中 至少有兩個(gè)元素 。你可以按 任意順序 返回答案。
數(shù)組中可能含有重復(fù)元素，如出現(xiàn)兩個(gè)整數(shù)相等，也可以視作遞增序列的一種特殊情況。
輸入輸出描述：
示例1：
輸入：nums = [4,6,7,7] 輸出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]
示例2：
輸入：nums = [4,4,3,2,1] 輸出：[[4,4]]
提示：
- 1 <= nums.length <= 15
- -100 <= nums[i] <= 100
思路和想法：
這道題目相較于上一道題子集II有什么區(qū)別，這道題是要在數(shù)組中找到不同的遞增子序列，所以不能對(duì)原數(shù)組進(jìn)行排序。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-618247.html
所以去重的方法，不能用原來(lái)的邏輯，這道題目還是進(jìn)行樹層去重，這里采用set來(lái)實(shí)現(xiàn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-618247.html
#include <bits/stdc++.h>
using namespace std;
/*
* 作者：希希霧里
* 491. 遞增子序列
* */
vector<vector<int>> result;
vector<int> path;
/*
* 函數(shù)： backtracing（）
* 輸入?yún)?shù)： s：輸入的字符串 index：數(shù)組元素下標(biāo)
* */
void backtracing(vector<int> &nums,int Index){
if(path.size() > 1){
result.push_back(path);
}
//回溯過(guò)程
unordered_set<int> uset; //使用set對(duì)本層元素進(jìn)行去重，新的一層會(huì)重新定義清空的
for (int i = Index; i < nums.size(); ++i) {
if((!path.empty() && nums[i] < path.back()) || uset.find(nums[i]) != uset.end()){
continue;
}
uset.insert(nums[i]);
path.push_back(nums[i]);
backtracing(nums,i + 1);
path.pop_back();
}
};
int main() {
result.clear();
path.clear();
int num;
vector<int> nums;
while(cin>>num){
nums.push_back(num);
if(getchar() == '\n'){
break;
}
}
backtracing(nums,0);
//輸出模式
cout << "[";
for (int i = 0; i < result.size(); ++i) {
cout << "[";
for (int j = 0; j < result[i].size(); ++j) {
cout<< result[i][j];
if(j != result[i].size() - 1) cout << ",";
}
cout << "]";
if(i != result.size() - 1) {cout << ",";}
}
cout << "]";
return 0;
}
/* 測(cè)試樣例
4 6 7 7
4 4 3 2 1
*
* */到了這里，關(guān)于代碼隨想錄-回溯算法（子集問(wèn)題）|ACM模式的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
