Day16-递归&回溯-有重复数组的子集

BUPTrenyi

发布于 2019-07-15 16:59:21

4790

发布于 2019-07-15 16:59:21

文章被收录于专栏：算法其实很好玩

一唠嗑

其实今天这道题本应该在昨天的，第二篇文章中的，奈何需求多而紧，着实没时间写第二篇文章了，你们可不要以为我是划水啊

熬过这周，下周的文章一定高产

二上题！

Q：已知一个数组，可能有重复元素，求所有的子集，要求不能重复。

举例：有nums = [2, 1, 2, 2]

则我需要return [[], [1], [1, 2], [1, 2, 2], [1, 2, 2, 2], [2], [2, 2], [2, 2, 2]]

需要注意，[2, 1, 2] 和 [1, 2, 2] 是重复的子集，不能都返回。

三冷静分析

在昨天那道题的思路下，我们思考：

这道题复杂在：

对于【2,1,2,2】在回溯过程中

取下标0,1,3，是【2,1,2】

取下标0,1,2，是【2,1,2】

取下标1,2,3，是【1,2,2】

这三组子集，均代表一种情况，故只能出现一次，怎么解决？

思路：

对于原数组【2,1,2,2】，将其排序后为【1,2,2,2】

此时无论怎么取下标，只能出现【1,2,2】这样的情况

会出现三次这种情况？怎么解决？

利用c++STL中的集合set去重的特性，我们只计入第一次的【1,2,2】

即排序 + 去重

四完整代码及注释

//
// Created by renyi on 2019/6/26.
//
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

void subsetsWithDuplicate(int i, vector<int> &nums, vector<int> &item, vector<vector<int>> &result, set<vector<int>> &res_set){
    if (i >= nums.size()){
        return;
    }
    item.push_back(nums[i]);
    if (res_set.find(item) == res_set.end()){//集合res_set中没有item，即去重逻辑，当第二次取到【1,2,2】时，将不会走if逻辑，result也不会追加item了，实现去重
        result.push_back(item);
        res_set.insert(item);
    }
    subsetsWithDuplicate(i + 1, nums, item, result, res_set);
    item.pop_back();
    subsetsWithDuplicate(i + 1, nums, item, result, res_set);
}

vector<vector<int>> subsets(vector<int> &nums){
    vector<int> item;
    vector<vector<int>> result;
    set<vector<int>> res_set;//去重的集合，需要将数组元素item插入集合中
    sort(nums.begin(), nums.end());//先将数组排序
    result.push_back(item);//结果中加入空集
    subsetsWithDuplicate(0, nums, item, result, res_set);
    return result;
}

int main(){
    vector<int> nums;
    nums.push_back(2);
    nums.push_back(1);
    nums.push_back(2);
    nums.push_back(2);
    vector<vector<int>> result;
    result = subsets(nums);
    for (int i = 0; i < result.size(); i++) {
        if (result[i].size() == 0){
            printf("[]");
        }
        for (int j = 0; j < result[i].size(); j++) {
            printf("[%d]", result[i][j]);
        }
        printf("\n");
    }
    return 0;
}

运行结果