全排列i

两种思路(均基于回溯)：

1. 用数组记录已访问过的元素
2. 利用交换

利用数组记录已访问过的元素

//
// Created by jt on 2020/8/31.
//
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
        dfs(res, vector<int>(), vector<int>(num.size(), 0), num);
        return res;
    }

    void dfs(vector<vector<int> > &res, vector<int> tmp, vector<int> visited, vector<int> &num) {
        if (tmp.size() == num.size()) { res.push_back(tmp); return; }
        for (int i = 0; i < num.size(); ++i) {
            if (visited[i] == 1) continue;
            visited[i] = 1;
            tmp.push_back(num[i]);
            dfs(res, tmp, visited, num);
            tmp.pop_back();
            visited[i] = 0;
        }
    }
};

利用交换

//
// Created by jt on 2020/8/31.
//
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > permute(vector<int> &num) {
        vector<vector<int> > res;
        dfs(res, num, 0);
        return res;
    }

    void dfs(vector<vector<int> > &res, vector<int> &num, int idx) {
        if (idx == num.size() - 1) { res.push_back(num); return; }
        for (int i = idx; i < num.size(); ++i) {
            swap(num[i], num[idx]);
            dfs(res, num, idx+1);
            swap(num[i], num[idx]);
        }
    }
};