LeetCode 046 Permutations 全排列「建议收藏」

全栈程序员-用户IM • 2022年9月20日下午1:16 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

Given a collection of distinct numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

方法一：

 1 class Solution {
 2 public:
 3      vector<vector<int> > permute(vector<int> &num) {
 4         vector<vector<int> > res;
 5         vector<int> out;
 6         int size=num.size();
 7         if(size==0||num.empty())
 8             return res;
 9         helper(num, 0,size, out, res);
10         return res;
11     }
12     void helper(vector<int> &num,int start,int size,vector<int> &out,vector<vector<int>> &res)
13     {
14         if(start==size-1)
15         {
16             for(int i=0;i<size;++i)
17                 out.push_back(num[i]);
18             res.push_back(out);
19             out.clear();
20         }
21         else
22         {
23             for(int i=start;i<size;++i)
24             {
25                 swap(num,start,i);
26                 helper(num,start+1,size,out,res);
27                 swap(num,start,i);
28             }
29         }
30     }
31     void swap(vector<int> &num,int i,int j)
32     {
33         int tmp=num[i];
34         num[i]=num[j];
35         num[j]=tmp;
36     }
37 };

方法二：

 1 class Solution {
 2 public:
 3     vector<vector<int>> permute(vector<int>& nums) {
 4         vector<vector<int>> res;
 5         helper(nums,0,res);
 6         return res;
 7     }
 8     void helper(vector<int> num,int start,vector<vector<int>> &res)
 9     {
10         if(start==num.size())
11         {
12             res.push_back(num);
13             return;
14         }
15         for(int k=start;k<num.size();++k)
16         {
17             swap(num[start],num[k]);
18             helper(num,start+1,res);
19         }
20     }
21 };