生成子集问题——迭代

问题描述

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

1
2
输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]

问题分析

策略选择

  • 算法思想：迭代求解

算法设计

  • 迭代思想，减治思想。每次选择一个元素，参与构建子集。
  • 首先对元素去重。记录重复元素的个数。如果多个重复元素分散在其他数组中没有意义。所有多个重复元素在一起的情况下组合到之前的解集中。
  • 这也算是一种动态规划的思想？每次都利用之前构建好的集合。构成新的解集集合。

算法分析

  • 时间复杂度：$O(n×2^n)$
  • 空间复杂度：$O(n)$.结果一般不算在空间复杂度当中。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> m(30, 0);
        vector<int> unique_nums;
        for (int i = 0; i < nums.size(); i++) {
            if (m[nums[i] + 10] == 0) {
                unique_nums.push_back(nums[i]);
            }
            m[nums[i] + 10]++;
        }
        result.push_back(vector<int>());
        for(int i=0;i<unique_nums.size();i++){
            int n = result.size();
            for(int j=0;j<n;j++){
                vector<int> vec(result[j]);
                for(int k=0;k<m[unique_nums[i]+10];k++){
                    vec.push_back(unique_nums[i]);
                    result.push_back(vec);
                }

            }
        }
        return result;

    }

};

生成子集问题——递归

问题分析

策略选择

  • 算法思想：迭代求解

算法设计

算法分析

  • 时间复杂度：$O(n×2^n)$
  • 空间复杂度：$O(n)$.结果一般不算在空间复杂度当中。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
void back(vector<int>nums, vector<vector<int>>& r, ctor<int>& m) {
        if (nums.size() == 0) {
            vector<int> vec1;
            r.push_back(vec1);
            return;
        }
        int temp = nums.back();
        nums.pop_back();
        back(nums, r, m);
        int n = r.size();
        for (int j = 0; j < n;j++) {
            vector<int> temp_v(r[j]);
            for (int i = 0; i < m[temp + 10]; i++) {
                temp_v.push_back(temp);
                r.push_back(temp_v);
            }
        }
        return;
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> m(30, 0);
        vector<int> unique_nums;
        for (int i = 0; i < nums.size(); i++) {
            if (m[nums[i] + 10] == 0) {
                unique_nums.push_back(nums[i]);
            }
            m[nums[i] + 10]++;
        }
        back(unique_nums, result, m);
        return result;
    }