登录
  • #刷题

leetcode 求subset的这个递归解法是什么意思

hanrui_542
5239
9
版里 戴方勤 leetcode题解里对求给定 set 的所有subset这题给了这么一个解法:
// LeetCode, Subsets[br][/br][br][/br]// 增量构造法,深搜,时间复杂度 O(2^n),空间复杂度 O(n)[br][/br][br][/br]class Solution {[br][/br][br][/br]public:[br][/br][br][/br]    vector<vector<int> > subsets(vector<int> &S) {[br][/br][br][/br]    sort(S.begin(), S.end()); // 输出要求有序[br][/br][br][/br]    vector<vector<int> > result;[br][/br][br][/br]    vector<int> path;[br][/br][br][/br]    subsets(S, path, 0, result);[br][/br][br][/br]    return result;[br][/br][br][/br]}[br][/br][br][/br]private:[br][/br][br][/br]    static void subsets(const vector<int> &S, vector<int> &path, int step, vector<vector<int> > &result) {[br][/br][br][/br]if (step == S.size()) {[br][/br][br][/br]result.push_back(path);[br][/br][br][/br]return;[br][/br][br][/br]}[br][/br][br][/br]// 不选 S[step][br][/br][br][/br]subsets(S, path, step + 1, result);[br][/br][br][/br]// 选 S[step][br][/br][br][/br]path.push_back(S[step]);[br][/br][br][/br]subsets(S, path, step + 1, result);[br][/br][br][/br]path.pop_back();[br][/br][br][/br]}[br][/br][br][/br]
这个解法怎么理解,这个怎么想出来的?想了半天不知道几个意思.oj通过,尽管效率差些

求指教!!!
9条回复
热度排序

发表回复