实现全排列 —— Leetcode(46)

Vinales, Cuba, by Sam Bark.

题目：全排列

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

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

来源： https://leetcode.com/problems/permutations/description/

解法一：C++ STL

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

解法二：backtracking

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        permutation(nums, 0, ans);
        return ans;
    }
    
    void permutation(vector<int>& nums, int begin, vector<vector<int>> &ans) {
        if (begin >= nums.size()) {
            ans.push_back(nums);
            return;
        }
        
        for (int i = begin; i < nums.size(); ++i) {
            swap(nums[i], nums[begin]);
            permutation(nums, begin + 1, ans); // 
            swap(nums[i], nums[begin]);
        }
    }
};