leetcode46——Permutations

题目大意：列出所给数字的全排列

分析：回溯法。这种枚举所有组合情况的题，首先考虑回溯。

代码：

方法一：逐步将数字添加到tmp中间集里。当tmp里面够个数了就将中间集加入结果集中。

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> tmp;
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> vis(nums.size());
        dfs(0,nums,vis);
        return ans;
    }
    void dfs(int k,vector<int>& nums,vector<int>& vis){
        if(k == nums.size()){
            ans.push_back(tmp);
            return;
        }
        for(int i = 0;i < nums.size();i++){
            if(!vis[i]){
                vis[i] = 1;
                tmp.push_back(nums[i]);
                dfs(k + 1,nums,vis);
                tmp.pop_back();
                vis[i] = 0;
            }
        }
    }
};

方法二：交换法。转载自https://www.cnblogs.com/wangxiaobao/p/5843945.html

class Solution {
private:
    vector<vector<int>> result;
    void helper(vector<int>& nums, int start, int end) {
        if (start == end) {
            result.push_back(nums);
        }
        for (int i = start; i <= end; ++i) {
            swap(nums[start], nums[i]);
            helper(nums, start + 1, end);
            swap(nums[start], nums[i]);
        }
    }
public:
    vector<vector<int>> permute(vector<int>& nums) {
        helper(nums, 0, nums.size() - 1);
        return result;
    }
};