题解 | C++#没有重复项数字的全排列#

一共三种方法：1.系统函数法 2.递归法 3.非递归，由已知排列找下一个全排列法

1.系统函数法

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

2.递归法

#include <vector>
#include <algorithm>

using namespace  std;

const  int MAXN = 10;

vector<int> temp;
vector<vector<int> > res;
bool visit[MAXN];
class Solution {
public:


    void dfs(int index, vector<int>& num) {
        if (index == num.size()) {
            res.push_back(temp);

        } else {
            for (int i = 0; i < num.size(); ++i) {
                if (visit[i]) {
                    continue;
                } else {
                    visit[i] = true;
                    temp.push_back(num[i]);
                    dfs( index + 1, num);
                    visit[i] = false;
                    temp.pop_back();
                }
            }
        }
    }
    vector<vector<int> > permute(vector<int>& num) {

        sort(num.begin(), num.end());
        dfs(0, num);
        return res;
    }
};

3.非递归，由已知排列找下一个全排列法

#include <algorithm>
#include <any>
#include "vector"
using namespace std;
vector<vector<int> >res;
class Solution {
public:
    bool GetNextPermutation(vector<int>& num) {
        int n = num.size();
        int index = n - 1;
        while (index >= 1 && num[index] < num[index - 1]) {
            index--;
        }
        index--;
        if (index < 0)return false;
        for (int i = n - 1; i > index; --i) {
            if (num[index] < num[i]) {
                swap(num[index], num[i]);
                break;
            }
        }
        reverse(num.begin() + index + 1, num.end());
        return true;
    }
    vector<vector<int> > permute(vector<int>& num) {
        sort(num.begin(), num.end());
        do {
            res.push_back(num);
        } while (GetNextPermutation(num));
        return res;
    }
};