「C++小例子」全排列【001】

共 3639字,需浏览 8分钟

 ·

2021-04-25 13:15

Part1题目

全排列

用1、2、3三个数字

可以组成多少个没有重复数字的三位数?

打印出所有的可能

Part2解答

参考Demo - C++

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

vector<int> temp; // 临时保存已经选择的数

// backtracking:回溯
void backtracking(vector<vector<int> > &res, vector<bool> &isused, vector<int> &nums)
{
    // 当temp数组的长度等于期望数组的长度时 return
    if (temp.size() == nums.size())
    {
        res.push_back(temp);
        return;
    }
    // 遍历所有选择
    for (int i = 0; i < nums.size(); ++i)
    {
        // 对没有选择过的元素再进行抉择:选择它|不选择它
        if (isused[i])
        {
            // 选择该元素 选择后标记该元素为已选择 同时进行下一元素的抉择
            temp.push_back(nums[i]);
            isused[i] = false;
            backtracking(res, isused, nums);
            // 回复原来状态:未选择 同时从temp中pop出
            isused[i] = true;
            temp.pop_back();
        }
    }
}

// permute:返回nums数组构成的全排列
vector<vector<int> > permute(vector<int> &nums)
{
    vector<vector<int> > res;
    vector<boolisused(nums.size(), true);
    backtracking(res, isused, nums);
    return res;
}

// 主函数
int main()
{
    // 初始化nums=[1,2,3]
    vector<int> nums;
    for (int i = 1; i <= 3; ++i)
    {
        nums.push_back(i);
    }

    // 结果返回值
    vector<vector<int> > ans;
    ans = permute(nums);

    // 打印结果
    for (int i = 0; i < ans.size(); ++i)
    {
        for (int j = 0; j < ans[i].size(); ++j)
        {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

运行结果

运行环境

Visual Studio Code

Part3结语

难度:medium

欢迎小伙伴们提供其余的解法

这里海轰提供的代码仅供参考,希望对您有所帮助,如有错误欢迎小伙伴指正~

我是海轰ଘ(੭ˊᵕˋ)੭,如果您觉得写得可以的话,请点个赞吧

谢谢支持❤️

写留言|查看留言

浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报