FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
leetcode/algorithms/cpp/permutations/permutations.cpp at master · wcoder0/leetcode · GitHub
wcoder0
leetcode
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
permutations
/
permutations.cpp
Copy path
More file actions
More file actions
Latest commit
History
History
History
112 lines (101 loc) · 2.48 KB
Breadcrumbs
leetcode
/
algorithms
/
cpp
/
permutations
/
permutations.cpp
Copy path
File metadata and controls
112 lines (101 loc) · 2.48 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
//
Source : https://oj.leetcode.com/problems/permutations/
//
Author : Hao Chen
//
Date : 2014-06-21
/*
*********************************************************************************
*
* Given a collection of 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], and [3,2,1].
*
*
*********************************************************************************
*/
#
include
<
stdio.h
>
#
include
<
stdlib.h
>
#
include
<
iostream
>
#
include
<
vector
>
using
namespace
std
;
/*
{ 1 2 3 }
{ 2 1 3 }
{ 3 2 1 }
{ 1 3 2 }
{ 2 3 1 }
{ 3 1 2 }
*/
/*
* The algroithm - Take each element in array to the first place.
*
* For example:
*
* 0) initalization
*
* pos = 0
* [1, 2, 3]
*
* 1) take each element into the first place,
*
* pos = 1
* [1, 2, 3] ==> [2, 1, 3] , [3, 1, 2]
*
* then we have total 3 answers
* [1, 2, 3], [2, 1, 3] , [3, 1, 2]
*
* 2) take each element into the "first place" -- pos
*
* pos = 2
* [1, 2, 3] ==> [1, 3, 2]
* [2, 1, 3] ==> [2, 3, 1]
* [3, 1, 2] ==> [3, 2, 1]
*
* then we have total 6 answers
* [1, 2, 3], [2, 1, 3] , [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1]
*
* 3) pos = 3 which greater than length of array, return.
*
*/
vector<vector<
int
> >
permute
(vector<
int
> &num) {
vector<vector<
int
> > vv;
vv.
push_back
(num);
if
(num.
size
() <
2
){
return
vv;
}
int
pos=
0
;
while
(pos<num.
size
()-
1
){
int
size = vv.
size
();
for
(
int
i=
0
; i<size; i++){
//
take each number to the first place
for
(
int
j=pos+
1
; j<vv[i].
size
(); j++) {
vector<
int
> v = vv[i];
int
t = v[j];
v[j] = v[pos];
v[pos] = t;
vv.
push_back
(v);
}
}
pos++;
}
return
vv;
}
int
main
(
int
argc,
char
** argv)
{
int
n =
3
;
if
(argc>
1
){
n =
atoi
(argv[
1
]);
}
vector<
int
> v;
for
(
int
i=
0
; i<n; i++) {
v.
push_back
(i+
1
);
}
vector<vector<
int
> > vv;
vv =
permute
(v);
for
(
int
i=
0
; i<vv.
size
(); i++) {
cout <<
"
{
"
;
for
(
int
j=
0
; j<vv[i].
size
(); j++){
cout << vv[i][j] <<
"
"
;
}
cout <<
"
}
"
<<endl;
}
return
0
;
}
Back
|
FazBrowse Home
|
New Git URL