이 leetcode 문제 사전 돌연변이에서 우리는 정렬 고유 한 정수의 모든 가능한 순열을 인쇄합니다.
차례
예
입력
arr [] = {1, 2, 3}
산출
+1 2 3 XNUMX
+1 3 2 XNUMX
+2 1 3 XNUMX
+2 3 1 XNUMX
+3 1 2 XNUMX
+3 2 1 XNUMX
입력
arr [] = {1, 2, 3, 4}
산출
1 2 3 4
1 2 4 3
2 1 3 4
2 1 4 3
1 3 2 4
1 3 4 2
2 3 1 4
2 3 4 1
1 4 3 2
1 4 2 3
2 4 3 1
2 4 1 3
3 2 1 4
3 2 4 1
4 2 3 1
4 2 1 3
3 1 2 4
3 1 4 2
4 3 2 1
4 3 1 2
3 4 1 2
3 4 2 1
4 1 3 2
4 1 2 3
Leetcode 문제 순열 알고리즘
모든 순열은 역 추적을 사용하여 생성 할 수 있습니다.
- 인덱스 l에서 r까지 배열의 모든 순열을 생성하려면 인덱스 l에서 요소를 수정하고 인덱스 l + 1에서 r까지 반복합니다.
- 인덱스 l에서 다른 요소를 역 추적하고 수정하고 인덱스 l + 1에서 r까지 반복합니다.
- 위의 단계를 반복하여 모든 순열을 생성합니다.
Leetcode 문제 순열에 대한 설명
arr [] = {1, 2, 3} 예제를 고려하십시오.
첫 번째 위치에있는 요소를 수정하면 1, 2 또는 3 중 세 가지 선택이 있습니다. 두 번째 수준 아래의 이미지는 이러한 상황을 나타냅니다. 두 번째 수준의 첫 번째 열에서 1은 첫 번째 위치에 고정되고, 두 번째 열에서 2는 첫 번째 위치에 고정되고 세 번째 열에서는 3이 첫 번째 위치에 고정됩니다.
첫 번째 위치에 요소를 고정한 후 두 번째 위치에 요소를 고정하고 두 번째 수준과 첫 번째 열의 경우를 고려합니다. 즉, {1, 2, 3}, 1이 첫 번째 위치에 고정되어 있으므로 2 또는 2 인 두 번째 위치에 대해 두 가지 선택이 있습니다. 두 번째 위치를 고정하면 자동으로 세 번째 위치가 고정됩니다. 설명은 위의 이미지를 참조하십시오.
모든 경우에이 작업을 수행하면 주어진 배열의 가능한 모든 순열이 생성됩니다.
JAVA 코드
public class LeetcodePermutations {
// Function to generate all the permutations from l to r
private static void permute(int[] arr, int l, int r) {
if (l == r) {
// Print this permutation
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;
}
for (int i = l; i <= r; i++) {
// Fix an element at index l
swap(arr, l, i);
// Recur for index l + 1 to r
permute(arr, l + 1, r);
// Back track
swap(arr, l, i);
}
}
// Function to swap element at index x and y of array arr
private static void swap(int arr[], int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
public static void main(String[] args) {
// Example
int arr[] = new int[] {1, 2, 3};
int n = arr.length;
// Generate permutations from index 0 to n - 1
permute(arr, 0, n - 1);
}
}
C ++ 코드
#include<bits/stdc++.h>
using namespace std;
// Function to swap element at index x and y of array arr
void swap(int *arr, int x, int y) {
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
// Function to generate all the permutations from l to r
void permute(int *arr, int l, int r, int n) {
if (l == r) {
// Print this permutation
for (int i = 0; i < n; i++) {
cout<<arr[i]<<" ";
}
cout<<endl;
return;
}
for (int i = l; i <= r; i++) {
// Fix an element at index l
swap(arr, l, i);
// Recur for index l + 1 to r
permute(arr, l + 1, r, n);
// Back track
swap(arr, l, i);
}
}
int main() {
// Example
int arr[] = {1, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
// Generate permutations from index 0 to n - 1
permute(arr, 0, n - 1, n);
return 0;
}
1 2 3 1 3 2 2 1 3 2 3 1 3 2 1 3 1 2
Leetcode 문제 순열에 대한 복잡성 분석
시간 복잡성 = 의 위에!)
여기서 n은 배열의 요소 수입니다.
