47. 全排列 II

难度中等709收藏分享切换为英文接收动态反馈

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 8
• -10 <= nums[i] <= 10

1. c++

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

class Solution{
public:
    void dfs(vector<vector<int>> &ret,const vector<int> &nums,vector<int> &cur_vec,bool *visited)
    {
        if (cur_vec.size() == nums.size())
        {
            ret.push_back(cur_vec);
            return;
        }

		set<int> sm_set;
		
        for (int i = 0; i < nums.size();++i)
        {
            if (visited[i] == true)//深度遍历
            {
                continue;
            }

            if (sm_set.count(nums[i]))//同层去重
            {
                continue;
            }
			
			sm_set.insert(nums[i]);
			
			cur_vec.push_back(nums[i]);
            visited[i] = true;
            
			dfs(ret,nums,cur_vec,visited);
            
			visited[i] = false;
            cur_vec.pop_back();
        }
    }

    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> cur_vec;
        bool visited[8] = {false};

        if (nums.size() <= 0)
        {
            return ret;
        }

        sort(nums.begin(),nums.end());
        dfs(ret,nums,cur_vec,visited);

        return ret;
    }
	
	void aux_print_v1ec(const vector<vector<int>> &nums)
	{
		for (auto itr:nums)
		{
			for (auto &iitr:itr)
			{
				cout<<iitr<<" ";
			}
			cout<<endl;
		}
	}
	
	void aux_print_vec(const vector<int> &nums)
	{
		for (auto &itr:nums)
		{
			cout<<itr<<" ";
		}
		cout<<endl;
	}
};

int main()
{
	Solution Cls;
	vector<int> nums;
	string input_line;
	
	while (getline(cin,input_line))
	{
		istringstream tmp_stream(input_line);
		
		int tmpint = 0;
		while (tmp_stream >> tmpint)
		{
			nums.push_back(tmpint);
		}
		
		vector<vector<int>> ret = Cls.permuteUnique(nums);
		
		Cls.aux_print_v1ec(ret);
		cout<<"type num: "<<ret.size()<<endl;
		
		nums.clear();
		ret.clear();
	}
	
	return 0;
}

STL

istream

(1) 从输入流is获取string,直到遇到字符delim
istream& getline (istream& is, string& str, char delim);
istream& getline (istream&& is, string& str, char delim);

(2) 和（1）相比，默认delim为换行符’\n’
istream& getline (istream& is, string& str);
istream& getline (istream&& is, string& str);

注意事项：

1.delim字符并不作为输入保存

2.若执行getline之前，str中有内容，则将被is的输入所替换。

3.若is达到了文件结束状态，那么getline也会停止。

set

1. set<int> var_set({1,2,3,4,5});var_set.find(2)返回的是指向这个元素的指针，var_set.count(2)是计算次数。set中的所有元素都是唯一的，所以count(key)的返回值只有0或1两种状态。