文章目錄
- 題目
- 思路
- 代碼
題目
給你一個整數陣列 nums ，陣列中的元素 互不相同 ，回傳該陣列所有可能的子集（冪集），
解集 不能 包含重復的子集，你可以按 任意順序 回傳解集，
示例1
輸入：nums = [1,2,3]
輸出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例2
輸入：nums = [0]
輸出：[[],[0]]
提示
1. 1 <= nums.length <= 10
2. -10 <= nums[i] <= 10
3. nums 中的所有元素 互不相同
思路
這題我們要注意題目中的要求，解集不能包含重復的子集，假如用示例1舉例子，就是我們在列舉完有關1的子集之后，就不再去關注1了，直接忽略它，遍歷的起點就需要從2再開始，對于[1 ,2, 3]這個例子我畫了一張解空間樹的圖，其中紅色的就是列舉的所有子集
通過圖我們可以很清晰的看到列舉完包含1的所有子集后，為了避免重復，之后遍歷的起點就是從1后一位開始的，遍歷完2,3也是一樣的，接下來我們看代碼
代碼
首先主函式中只是做一些基本作業然后直接進入dfs函式
class Solution {
public:
int n;
vector<vector<int>> ans;
vector<int> temp;
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
dfs(n , nums, 0);
return ans;
}
};
然后是dfs函式，這個dfs函式沒有出口條件，這意味著每進入一層遞回，我們都會把當前選中的集合加入答案中
void dfs(int n, vector<int>& nums, int u) {
ans.push_back(temp);
}
然后便是回圈遍歷nums陣列，只不過這里要注意，遍歷的起點并不是0，而是我們主函式中傳入的引數，這個引數就用來控制當前遞回中遍歷的起點
for(int i = u; i < n; i++) {}
而這里還有一個要注意得點就是我們在做回溯的時候，往下一層傳入的u的值并不是u + 1，而是i + 1，因為如果是u + 1的話，那么i的值比u + 1還大之后，進入下一層遞回卻還是從u + 1作為遍歷起點，就會使一部分子集重復，而傳入的是i + 1的話，不論i的值為多少，下一層遞回中遍歷的起點都是i的下一位i + 1
for(int i = u; i < n; i++) {
temp.push_back(nums[i]);
dfs(n, nums, i + 1);
temp.pop_back();
}
然后是完整代碼：
class Solution {
public:
int n;
vector<vector<int>> ans;
vector<int> temp;
void dfs(int n, vector<int>& nums, int u) {
ans.push_back(temp);
for(int i = u; i < n; i++) {
temp.push_back(nums[i]);
dfs(n, nums, i + 1);
temp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
n = nums.size();
dfs(n , nums, 0);
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/353387.html
標籤：其他
上一篇：【資料結構】TopK問題