首页 > 代码库 > LeetCode78 Subsets

LeetCode78 Subsets

题目:

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets. (Medium)

For example,
If nums = [1,2,3], a solution is:

[  [3],  [1],  [2],  [1,2,3],  [1,3],  [2,3],  [1,2],  []]

分析: 回溯法或位运算。

回溯的思路就是每个元素可以要可以不要,然后进一步dfs下去。

代码:

 1 class Solution { 2 private: 3     void helper(vector<int>& nums, vector<int>& temp, int start, vector<vector<int>>& result) { 4         if (start == nums.size()) { 5             return; 6         } 7         temp.push_back(nums[start]); 8         result.push_back(temp); 9         helper(nums, temp, start + 1, result);10         temp.pop_back();11         helper(nums, temp, start + 1, result);12     }13 public:14     vector<vector<int>> subsets(vector<int>& nums) {15         vector<vector<int>> result;16         vector<int> temp;17         result.push_back(temp);18         helper(nums, temp, 0, result);19         return result;20     }21 };

 

LeetCode78 Subsets