90. Subsets II

題目

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

           

解析

• [LeetCode] Subsets II 子集合之二 使用非遞歸疊代和遞歸實作

從前往後周遊，保留下目前已經計算好的組合集合。對目前i号元素的加入，就是有i和沒有i的場景。沒有i的場景就是已有的集合。有i的就是對已有的集合追加上i後的集合。兩個的并集就是加入i之後的結果。

如果i和上一個元素是重複的，則隻需要考慮i-1加入過集合的那部分子集。對于不包含i-1元素的場景來說，這部分子集加入i的結果集，和已有的加入過i-1的結果集是重複的。所有跳過這部分就可以了。

// 90. Subsets II
class Solution_90 {
public:

	void dfs(vector<vector<int>> &res,vector<int> &out,vector<int>&nums,int pos)
	{
		res.push_back(out);

		for (int i = pos; i < nums.size();i++)
		{
			out.push_back(nums[i]);
			dfs(res, out, nums, i + 1);
			out.pop_back();
			while ((i+1)<nums.size()&&nums[i+1]==nums[i])
			{
				i++;
			}
		}
		return;
	}

	vector<vector<int>> subsetsWithDup(vector<int>& nums) {

		vector<vector<int>> res;
		vector<int> out;
		if (nums.empty())
		{
			return res;
		}
		sort(nums.begin(),nums.end());

		dfs(res, out, nums, 0);

		return res;

	}
};

           

題目來源

C/C++基本文法學習

STL

C++ primer