Leetcode 순열


난이도 중급
자주 묻는 질문 아마존 Apple ByteDance 이베이 페이스북 서비스 구글 Microsoft 신탁
역 추적

이 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 문제 순열 알고리즘

모든 순열은 역 추적을 사용하여 생성 할 수 있습니다.

  1. 인덱스 l에서 r까지 배열의 모든 순열을 생성하려면 인덱스 l에서 요소를 수정하고 인덱스 l + 1에서 r까지 반복합니다.
  2. 인덱스 l에서 다른 요소를 역 추적하고 수정하고 인덱스 l + 1에서 r까지 반복합니다.
  3. 위의 단계를 반복하여 모든 순열을 생성합니다.

Leetcode 문제 순열에 대한 설명

arr [] = {1, 2, 3} 예제를 고려하십시오.

첫 번째 위치에있는 요소를 수정하면 1, 2 또는 3 중 세 가지 선택이 있습니다. 두 번째 수준 아래의 이미지는 이러한 상황을 나타냅니다. 두 번째 수준의 첫 번째 열에서 1은 첫 번째 위치에 고정되고, 두 번째 열에서 2는 첫 번째 위치에 고정되고 세 번째 열에서는 3이 첫 번째 위치에 고정됩니다.

Leetcode 순열

첫 번째 위치에 요소를 고정한 후 두 번째 위치에 요소를 고정하고 두 번째 수준과 첫 번째 열의 경우를 고려합니다. 즉, {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은 배열의 요소 수입니다.

참조