[leetcode]78.サブセット
5568 ワード
重複要素を含まない整数配列numsのセットを指定し、その配列の可能なすべてのサブセット(べき乗セット)を返します.
説明:解セットに重複するサブセットを含めることはできません.
例:
考え方:DFS遡及
一時配列tempを定義し、dfsに戻るたびにtempを答え配列に押し込み、dfsは現在の一時配列がどこから始まるかを示す開始ノードを保存します.
ACコード:(C++)
説明:解セットに重複するサブセットを含めることはできません.
例:
: nums = [1,2,3]
:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
考え方:DFS遡及
一時配列tempを定義し、dfsに戻るたびにtempを答え配列に押し込み、dfsは現在の一時配列がどこから始まるかを示す開始ノードを保存します.
ACコード:(C++)
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
vector<int> temp;
dfs(ans, nums, 0, temp);
return ans;
}
void dfs(vector<vector<int>>& ans, vector<int>& nums, int startPoint,
vector<int> temp) {
ans.push_back(temp);
for (int i = startPoint; i < nums.size(); i++) {
temp.push_back(nums[i]);
dfs(ans, nums, i + 1, temp);
temp.pop_back();
}
}
};