LeetCode Permutations II

本文主要是介绍LeetCode Permutations II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

题意：求不重复的所有序列。

思路：dfs，但是要注意一点的是如果去重：排序后，可以为每个数都设置一个vis表示是否访问过，当两个相邻的数一样且前一个被访问过了，那么这个数才能使用，才能避免重复。

class Solution {
public:int vis[110], a[110];vector<vector<int> > ans;void dfs(int cur, int n, vector<int> &num) {if (cur == n) {vector<int> tmp;for (int i = 0; i < n; i++) tmp.push_back(a[i]);ans.push_back(tmp);return;}for (int i = 0; i < n; i++) if (!vis[i]) {if (i != 0 && num[i] == num[i-1] && vis[i-1]) continue;vis[i] = 1;a[cur] = num[i];dfs(cur+1, n, num);vis[i] = 0;}}vector<vector<int> > permuteUnique(vector<int> &num) {sort(num.begin(), num.end());ans.clear();memset(vis, 0, sizeof(vis));dfs(0, num.size(), num);return ans;}
};

这篇关于LeetCode Permutations II的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---