欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

#leetcode刷题之路46-全排列

程序员文章站 2023-11-06 09:59:46
给定一个没有重复数字的序列,返回其所有可能的全排列。示例:输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]] 两种方法,第一种用了STL中的函数,第二种用递归+回溯,我个人很喜欢第二种方法 ......

给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

 

两种方法,第一种用了stl中的函数,第二种用递归+回溯,我个人很喜欢第二种方法

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//vector<vector<int>> permute(vector<int>& nums) {
//    sort(nums.begin(), nums.end());
//    vector<vector<int>> a;
//    do {
//        a.push_back(nums);
//    } while (std::next_permutation(nums.begin(), nums.end()));
//    return a;
//}

void backtracking(vector<int>& nums,int start,vector<int> &temp,vector<vector<int>> &ans) {

    if (!nums.size()) return;
    if (start>=nums.size())
    {
        ans.push_back(temp);
        return;
    }
    for (int i=start; i<nums.size();i++)
    {
        swap(nums[i],nums[start]);
        temp.push_back(nums[start]);
        backtracking(nums, start+1, temp,ans);// 递归求解
        temp.pop_back();//回溯,不影响此次的循环
        swap(nums[i], nums[start]);//回溯不影响此次的循环
    }
}
vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> ans;
    vector<int> curseq;
    backtracking(nums, 0, curseq,ans);
    return ans;
}

int main() {
    vector<int> nums={1,2,3};
    int ans=permute(nums).size();
    std::cout << ans << std::endl;
    return 0;
}