0046. 全排列 [Medium] [Permutations].md

46. 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]
]

---

题目：给定一个无重复元素的数组nums,求解这些元素的全排列。

思路：回溯的思想。假设p为数组nums的一种排列，数组的长度nums.size()记为n，因为nums中都是无重复的元素，那么在p的每个位置上可能的取值有n个，递归的深度递归的深度由数组的长度决定为n，当p中已经有n个元素时，得到了一种排类，回溯返回。同时在求解一个排列时，需要一个标志位数组来表明该元素是否已经被选择过了。比如在第一个位置p[0]上我们已经选择了nums[0]，那么p[1]就应该排除nums[0]。

思路：全排列也可以理解为当前位置元素和后面每个元素的交换，对nums中每个位置递归进行上述操作。见具体分析。

工程代码下载

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> res;
        int n = nums.size();
        if(n == 0) return res;
        vector<bool> used(n);
        vector<int> vec;
        helper(nums, res, vec, used);
        return res;
    }
private:
    void helper(vector<int>& nums, vector<vector<int>>& res, vector<int>& vec, vector<bool>& used){
        if(vec.size() == nums.size()){
            res.push_back(vec);
            return;
        }

        for(int i = 0; i < nums.size(); ++i){
            if(used[i])
                continue;
            vec.push_back(nums[i]);
            used[i] = true;
            helper(nums, res, vec, used);
            used[i] = false;
            vec.pop_back();
        }

        return;
    }

public:
    //另外一种全排列的方法。每个值和后面每个值交换
    void swap_two(vector<vector<int>> &ans, vector<int>&nums, int start) {
        if (start == nums.size())
        {
            ans.push_back(nums);
            return;
        }
        else
        {
            for (size_t i = start; i < nums.size(); i++)
            {
                swap(nums[start], nums[i]);
                swap_two(ans, nums, start + 1);
                swap(nums[start], nums[i]);
            }
        }
    }
};

int main()
{
    Solution sln;
    vector<int> test_case{ 1,2,3 };
    vector<vector<int> > ans = sln.permute(test_case);
    for (const auto & i : ans)
    {
        for (const auto & j : i)
            cout << j << ' ';
        cout << endl;
    }
    ans.clear();
    cout << endl;

    sln.swap_two(ans, test_case, 0);
    for (const auto & i : ans)
    {
        for (const auto & j : i)
            cout << j << ' ';
        cout << endl;
    }
    std::cout << "Hello World!\n";
}