首页 > 代码库 > LeetCode90 Subsets II

LeetCode90 Subsets II

2024-08-17 09:49:41   216人阅读

题目：

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets. （Medium）

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

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

分析：

这次相较于subsetsI有了重复元素，所以一个简单的思路就是判重，重复的不添加到结果中（但时间复杂度稍高，不过既然是回溯，也就不太在乎时间复杂度了）

代码：

 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         vector<int> input = temp;
 9         sort(input.begin(), input.end());
10         if (find(result.begin(), result.end(), input) == result.end()) {
11             result.push_back(input);
12         }
13         helper(nums, temp, start + 1, result);
14         temp.pop_back();
15         helper(nums, temp, start + 1, result);
16     }
17 public:
18     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
19         vector<vector<int>> result;
20         vector<int> temp;
21         result.push_back(temp);
22         helper(nums, temp, 0, result);
23         return result;
24     }
25 };

 

LeetCode90 Subsets II


联系
我们