46.Permutations

Tags: Medium Backtracking

Links: https://leetcode.com/problems/permutations/

---

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

---

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        vector<vector<int>> res;
        sort(nums.begin(), nums.end());
        do {
            res.push_back(nums);
        } while (next_permutation(nums.begin(), nums.end()));

        return res;
    }
};

题目里数组初始并不是有序的，所以需要先排序。看了题目的标签，让用backtracking，那么应该本意是不让用标准库算法的，所以写一个DFS。

其实这个和《挑战程序设计竞赛》里2.1.6 特殊状态的枚举很接近。

class Solution {
    vector<vector<int>> res;
    vector<bool> used;
    vector<int> perm;

public:
    vector<vector<int>> permute(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        used.resize(n, false);
        perm.resize(n);

        permutation(0, n, nums);

        return res;
    }

    void permutation(int pos, int n, vector<int> & nums)
    {
        if (pos == n) {
            res.push_back(perm);
            return;
        }

        for (int i = 0; i < n; ++i) {
            if (!used[i]) {
                perm[pos] = nums[i];
                used[i] = true;
                permutation(pos + 1, n, nums);
                used[i] = false;
            }
        }
    }

};