Leetcode
Array
Backtracking
Bit Manipulation
题目¶
Given a set of distinct integers, nums, return all possible subsets (the power set).
Note: The solution set must not contain duplicate subsets.
Example:
Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]
分析¶
幂集(power set)的wikipedia页面
其实和sublists思路一样。以第i个元素是否出现在output中为判断条件，构建decision tree。使用backtracking。
class Solution { public: void subsetsHelper(int& n, int position, vector<int>& nums, vector<int>& chosen, vector<vector<int>>& res){ if (position==n){ res.push_back(chosen); return; }else{ //choose and explore subsetsHelper(n, position+1, nums, chosen, res); // 不选择 int s = nums[position]; chosen.push_back(s); subsetsHelper(n, position+1, nums, chosen, res); // 选择 //unchoose chosen.pop_back(); } } vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int>> res; vector<int> chosen; int n = nums.size(); subsetsHelper(n, 0, nums, chosen, res); return res; } };
不过也可以使用传统的backtracking，但是其base case始终发生。
class Solution { public: vector<vector<int> > subsets(vector<int> &nums) { vector<vector<int> > res; vector<int> vec; subsets(res, nums, nums.size(), vec, 0); return res; } private: void subsets(vector<vector<int> > &res, vector<int> &nums, int n, vector<int> &vec, int begin) { res.push_back(vec); for (int i = begin; i < n; ++i) { vec.push_back(nums[i]); subsets(res, nums, n, vec, i + 1); vec.pop_back(); } } };
近期评论