• LeetCode 90. 子集 II(Subsets II)


    题目描述

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

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

    示例:

    输入: [1,2,2]
    输出:
    [
      [2],
      [1],
      [1,2,2],
      [2,2],
      [1,2],
      []
    ]

    解题思路

    利用回溯的思想,对于每个元素分为两种情况:不添加到子集或者添加到子集。注意因为有重复元素,所以先对整个数组排序使得重复元素到一起,若遇到重复元素,则单独处理,针对每种可能的组合情况添加或不添加到子集中。

    代码

     1 class Solution {
     2 public:
     3     vector<vector<int>> subsetsWithDup(vector<int>& nums) {
     4         vector<vector<int>> res;
     5         vector<int> temp;
     6         sort(nums.begin(), nums.end());
     7         subsets(nums, 0, temp, res);
     8         return res;
     9     }
    10     void subsets(vector<int> nums, int idx, vector<int> temp, vector<vector<int>> &res){
    11         if(idx == nums.size()){
    12             res.push_back(temp);
    13             return;
    14         }
    15         if(idx < nums.size() - 1 && nums[idx] == nums[idx + 1]){
    16             int i = idx;
    17             while(i < nums.size() - 1 && nums[i] == nums[i + 1]) i++;
    18             while(idx <= i){
    19                 subsets(nums, i + 1, temp, res);
    20                 temp.push_back(nums[idx++]);
    21             }
    22             subsets(nums, i + 1, temp, res);
    23         }
    24         else{
    25             subsets(nums, idx + 1, temp, res);
    26             temp.push_back(nums[idx]);
    27             subsets(nums, idx + 1, temp, res);
    28         }
    29     }
    30 };
  • 相关阅读:
    窗口生效函数UpdateData
    查找内容grep命令
    终止函数 atexit()
    根据名字杀死进程Killall
    修改系统时间为UTC时间
    转 proc文件
    NTP算法
    转载,网线的深刻理解
    js完成密码输入为空,和两次输入不一致
    CSS初步了解
  • 原文地址:https://www.cnblogs.com/wmx24/p/9505394.html
一二三 - 开发者的网上家园