DFS递归实现:
递归的终止条件多种多样。可以用条件语句,也可以用while(),for()循环,本题中是在for()循环中。递归只是单纯的自己调用自己。在DFS中需要回溯。如何确定回溯的表达式很重要。
class Solution { public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> result; vector<int> list; if(nums.empty()) return result; sort(nums.begin(),nums.end());//用sort函数,为vector<int>里的元素排序 dfs(nums,0,list,result); return result; } void dfs(vector<int>& nums,int p,vector<int>& list,vector<vector<int>>& result){ result.push_back(list); for(int i=p;i<nums.size();i++){ list.push_back(nums[i]); dfs(nums,i+1,list,result); list.pop_back(); } } };
本题解法2: 位运算