刷题78. Subsets

一、题目说明

题目78. Subsets，给一列整数，求所有可能的子集。题目难度是Medium！

二、我的解答

这个题目，前面做过一个类似的，相当于求闭包：

刷题22. Generate Parentheses

算了，用最简单的回溯法吧：

class Solution{

	public:

		void dfs(vector<int>& nums,int start){

			r.push_back(path);

			for(int i=start;i<len;i++){

				path.push_back(nums[i]);

				dfs(nums,i+1);

				path.pop_back();

			}

		}

		vector<vector<int>> subsets(vector<int>& nums){

			this->len = nums.size();

			dfs(nums,0);

			return r;

		}

	private:

		vector<vector<int>> r;

		vector<int> cur;

		vector<int> path;

		int len;

};

性能如下：

Runtime: 8 ms, faster than 61.43% of C++ online submissions for Subsets.

Memory Usage: 9.2 MB, less than 72.88% of C++ online submissions for Subsets.

三、优化措施

当然，用 刷题22. Generate Parentheses 中的方法也可以的。