LeetCode 90.Subsets II (子集 II)

梦里梦外; 2022-05-10 10:24 268阅读 0赞

题目描述：

给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

  1. 输入: [1,2,2]
  2. 输出:
  3. [
  4.   [2],
  5.   [1],
  6.   [1,2,2],
  7.   [2,2],
  8.   [1,2],
  9.   []
  10. ]

AC C++ Solution：

回溯法：

  1. class Solution {
  2. public:
  3.     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
  4.         sort(nums.begin(), nums.end());
  5.         vector<int> ivec;
  6.         vector<vector<int>> res;
  7.         subset(nums, ivec, 0, res);
  8.         return res;
  9.     }
  10.     void subset(vector<int> nums, vector<int>& ivec, int index, vector<vector<int>>& res){
  11.         res.push_back(ivec);
  12.         for(int i=index; i<nums.size(); i++){
  13.             ivec.push_back(nums[i]);
  14.             subset(nums, ivec, i+1, res);
  15.             while(i+1<nums.size() && nums[i]== nums[i+1])
  16.                 i++;
  17.             ivec.pop_back();
  18.         }
  19.     }
  20. };

发表评论

表情：
评论列表 （有 0 条评论，268人围观）

还没有评论，来说两句吧...

相关阅读

    相关 leetcode 90 子集II

    给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集。 示例: 输入: \[1,2,2\] 输出: \[

    r囧r小猫r囧r小猫/ 0 赞/ 104 阅读