给定可能包含重复项的整数数组，请返回所有子集。 CPP解决方案

Example:
Input: [1,2,2]
Output:
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

解决这个问题之前，先看看类似的问题 子集.

与子集1问题类似，我们可以通过2种方法解决此问题。

1. 迭代式
2. 递归/回溯。

我们将在这里讨论这两种解决方案。

因此，“子集”问题与唯一的区别是输入列表中允许重复项。

因此，我们进行以下2个更改：

1. 对输入数组进行排序，以便将重复的元素彼此相邻放置。
2. 然后我们检查上一个元素是否与当前元素相同，我们跳过该元素。

C ++解决方案

#include<iostream>
#include<vector>

using namespace std;

vector<vector<int>> get_subsets_with_dup_iterative(vector<int>& input_set) 
{
  sort(input_set.begin(), input_set.end());//change 1
  vector<vector<int>> result_set(1, vector<int>());
  int start = 0;
  int n = 0;
  for (int i = 0; i < input_set.size(); i++) 
  {
    start = ((i > 0) && (input_set[i] == input_set[i - 1])) ? n : 0;
    n = result_set.size();
    for (int j = start; j < n; j++) 
    {
      result_set.push_back(result_set[j]); 
      result_set.back().push_back(input_set[i]);
    }
  }
  return result_set;
}


void subsets(vector<int>& nums, int start, vector<int>& temp, vector<vector<int>>& final_set) 
{
  final_set.push_back(temp);
  for (int i = start; i < nums.size(); i++) 
  {
    if ((i == start) || (nums[i] != nums[i - 1]))  // change 2
    {
      temp.push_back(nums[i]);
      subsets(nums, i + 1, temp, final_set);
      temp.pop_back();
    }
  }
}


vector<vector<int>> get_subsets_with_dup_backtrack(vector<int>& nums) 
{
  sort(nums.begin(), nums.end()); // change 1
  vector<vector<int>> final_set;
  vector<int> temp;
  subsets(nums, 0, temp, final_set);
  return final_set;
}



int main()
{
  vector<int> input_set = {1, 2, 2};

  vector< vector<int> >result = get_subsets_with_dup_iterative(input_set);
  //vector< vector<int> >result = get_subsets_with_dup_backtrack(input_set);



  for (int i = 0; i < result.size(); i++)
  {
    for (int j = 0; j < result[i].size(); j++)
    {
      cout<< result[i][j]<<" ";
    }
    cout<<endl;
  }
}

输出：

1
2
1 2
2 2
1 2 2

该网站上可用的教程列表：