순열 Leetcode 솔루션  


난이도 중급
자주 묻는 질문 어도비 벽돌 아마존 Apple 골드 피처 블룸버그 게시물에서 ByteDance 이베이 페이스북 서비스 가레 나 에서 GoDaddy 골드만 삭스 구글 링크드 인 Microsoft 신탁 세일즈 포스 SAP 동네 짱 VM웨어 월마트 연구소 Yahoo
알고리즘 역 추적 코딩 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions

문제 Permutations Leetcode Solution은 간단한 정수 시퀀스를 제공하고 완전한 벡터를 반환하거나 정렬 주어진 시퀀스의 모든 순열의. 따라서 문제를 해결하기 전에. 우리는 순열에 익숙해야합니다. 따라서 순열은 주어진 정수의 배열 일뿐입니다. 그래서 우리가 시퀀스의 모든 순열이 필요하다고 말할 때. 우리는 주어진 시퀀스의 가능한 모든 배열을 인쇄하거나 반환해야 함을 의미합니다. 더 나은 이해를 위해 몇 가지 예를 살펴 보겠습니다.

Given sequence: [1,2,3]
Permutations: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

설명 : 1, 2, 3을 순서대로 쓸 수있는 모든 방법이 출력으로 제공되었습니다. 순열에서 6, 1, 2을 쓰는 방법은 총 3 가지가 있습니다.

[0,1]
[[0,1],[1,0]]

설명 : 2, 0을 쓰는 방법은 두 가지뿐입니다.

순열 Leetcode 솔루션에 대한 역 추적 접근 방식  

순열 Leetcode 솔루션

문제 Permutations Leetcode Solution은 주어진 시퀀스의 모든 순열을 생성하도록 요청했습니다. 일반적으로 순열을 생성해야하거나 시퀀스 재귀가 핵심입니다. 그러나 여기서 재귀 또는 역 추적은 약간 까다 롭습니다. 한 가지 방법은 선택되지 않은 요소에서 요소를 선택하여 답의 끝에 배치하는 것입니다. 이 방법은 순열을 생성하고 어떻게 든이 순열이 생성되었으며 반복해서는 안된다는 것을 기억해야합니다. 그러나이를 수행하는 대신 작업을 수행하는 간단한 방법을 찾으려고합니다. 요소를 선택하고 현재 요소로 바꾸면 어떨까요? 그런 다음 재귀 호출을 수행하여 현재 인덱스 뒤에 인덱스 하나의 시퀀스에 대한 모든 순열을 생성합니다.

참조
두 개의 정렬 된 연결 목록 병합

순열 생성이 완료되면 인덱스 하나를 앞 당깁니다. 선택한 요소를 제거한 다음 다른 요소를 선택하고 절차를 반복합니다. 이런 식으로 사용하지 않은 각 요소를 현재 위치에 한 번 이상 배치했는지 확인합니다. 그리고 우리는 더 작은 하위 문제를 재귀 적으로 호출했기 때문입니다. 더 작은 하위 문제는 현재 인덱스 바로 다음에 시작하는 시퀀스에 대한 순열을 생성하는 것입니다. 이러한 순열을 현재 순열에 추가하면 현재 인덱스에 요소 집합이있는 순열 집합이 완료됩니다. 이런 식으로 배열을 왼쪽에서 오른쪽으로 계속 탐색하고 문제를 더 작은 하위 문제로 나눕니다. 필요에 도달하면 가능한 순열을 생성하고 답에 추가합니다.

역 추적 코드  

순열 Leetcode 솔루션을위한 C ++ 코드

#include <bits/stdc++.h>
using namespace std;

void permutationUtil(vector<int> &nums, int i, int &numsSize, vector<vector<int>> &answer){
    if(i == numsSize){
        answer.push_back(nums);
    }
    for(int j = i; j < numsSize; j++){
        swap(nums[i], nums[j]);
        permutationUtil(nums, i+1, numsSize, answer);
        swap(nums[i], nums[j]);
    }
}

vector<vector<int>> permute(vector<int>& nums) {
    vector<vector<int>> answer;
    int numsSize = nums.size();
    permutationUtil(nums, 0, numsSize, answer);
    return answer;
}

int main(){
    vector<int> nums({1, 2, 3});
    vector<vector<int>> answer = permute(nums);
    for(auto i: answer){
        for(auto j: i)
            cout<<j<<" ";
        cout<<"\t";
    }
}
1 2 3   1 3 2   2 1 3   2 3 1   3 2 1   3 1 2

순열 Leetcode 솔루션을위한 자바 코드

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main {
    public static void permutationUtil(List<Integer> nums, int i, int numsSize, List<List<Integer>> answer){
        if(i == numsSize){
            answer.add(new ArrayList<Integer>(nums));
        }
        for(int j = i; j < numsSize; j++){
            Collections.swap(nums, i, j);
            permutationUtil(nums, i+1, numsSize, answer);
            Collections.swap(nums, i, j);
        }
    }
 
    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> answer = new LinkedList();
        int numsSize = nums.length;
        List<Integer> list = new ArrayList<Integer>();
        for(int i=0;i<numsSize;i++)
            list.add(nums[i]);
        permutationUtil(list, 0, numsSize, answer);
        return answer;
    }
 
    public static void main(String[] args){
    	int nums[] = {1, 2, 3};
    	List<List<Integer>> answer = permute(nums);
    	System.out.println(answer.toString());
    }
}
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]

복잡성 분석  

시간 복잡성

O (시그마 (P (N, K)), 여기서 P는 n의 k 순열 또는 부분 순열입니다. 좀 더 공식적으로, P (N, k) = (N!) / ((Nk)!).

참조
하위 배열 Leetcode 솔루션을 반대로하여 두 배열을 동일하게 만들기

공간 복잡성

의 위에!), 가능한 모든 솔루션을 저장해야하므로 N! 여기서 N은 배열의 크기입니다.