[LeetCode] permutation sequence

https://leetcode.com/problems/permutation-sequence/

 

 

문제 파악

1~n 까지의 수의 순열을 구하고, 그 중 k번째 순열을 문자열 형태로 리턴

• 1 <= n <= 9
• 1 <= k <= n!

접근 방법

-순열 문제

코드 구현

import java.util.*;
class Solution {
    public String getPermutation(int n, int k) {
        String answer="";
        List<List<String>> permutations = new ArrayList<>();
        boolean[] visited = new boolean[n];
        String[] arr = new String[n];
        for(int i=1;i<=n;i++){
            arr[i-1] = String.valueOf(i);
        }
        backtrack(permutations,new ArrayList<>(),visited,n,arr);
        for(String v:permutations.get(k-1)){
            answer+=v;
        }
        return answer;
    }
    public void backtrack(List<List<String>> permutations,List<String> curr,boolean[] visited,int n,String[] arr){
        //base case
        if(curr.size() == n){
            permutations.add(new ArrayList<>(curr));
            return;
        }

        //recursive
        for(int i=0;i<n;i++){
            if(curr.contains(arr[i])) continue;
            curr.add(arr[i]);
            visited[i]=true;
            backtrack(permutations,curr,visited,n,arr);
            curr.remove(curr.size()-1);
            visited[i]=false;
        }
    }
}

배우게 된 점

-결과값에 아무것도 안나올 시, 재귀 호출 매개변수를 잘 주었는지 확인해보자.