设为首页 加入收藏

TOP

#leetcode刷题之路46-全排列
2019-04-07 22:07:46 】 浏览:29
Tags:#leetcode 46- 排列

给定一个没有重复数字的序列,返回其所有可能的全排列。
示例:
输入: [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;
}

 


编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇博弈论之SG函数 下一篇#leetcode刷题之路48-旋转图像

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }