全排列ii

三种方法：

1. 回溯——基于辅助数组
2. 回溯——基于交换
3. 基于库函数next_permutation

方法一：基于辅助数组

//
// Created by jt on 2020/9/1.
//
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        vector<int> visited(num.size(), 0);
        sort(num.begin(), num.end());
        dfs(res, num, visited, vector<int>());
        return res;
    }

    void dfs(vector<vector<int> > &res, vector<int> &num, vector<int> &visited, vector<int> vec) {
        if (vec.size() == num.size()) { res.push_back(vec); return; }
        for (int i = 0; i < num.size(); ++i) {
            if (visited[i] == 1) continue;
            //举例 112
            if (i>0 && num[i-1]==num[i] && !visited[i-1]) continue;
            visited[i] = 1;
            vec.push_back(num[i]);
            dfs(res, num, visited, vec);
            vec.pop_back();
            visited[i] = 0;
        }
    }
};

方法二：基于交换

//
// Created by jt on 2020/9/1.
//
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        set<vector<int>> st;
        dfs(st, num, 0);
        for (auto vec : st) res.push_back(vec);
        return res;
    }

    void dfs(set<vector<int> > &st, vector<int> &num, int idx) {
        if (idx == num.size()-1) { st.insert(num); return; }
        for (int i = idx; i < num.size(); ++i) {
            if (i != idx && num[i] == num[idx]) continue; // 剪枝
            swap(num[i], num[idx]);
            dfs(st, num, idx+1);
            swap(num[i], num[idx]);
        }
    }
};

方法三：基于库函数

//
// Created by jt on 2020/9/1.
//
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

class Solution {
public:
    vector<vector<int> > permuteUnique(vector<int> &num) {
        vector<vector<int> > res;
        sort(num.begin(), num.end());
        do{
            res.push_back(num);
        } while (next_permutation(num.begin(), num.end()));
        return res;
    }
};