[leetcode] 46. Permutations

https://leetcode.com/problems/permutations/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 해석

배열이 주어지면 순열을 아무 순서로나 반환하면 되는 문제였다.

 

통과 코드

풀이: Back-tracking

백트래킹을 이용해서 이미 사용한 인덱스인지 체크했고 체크해야하는 인덱스 순서를 파라미터로 보내서 체크할 수 있도록 했다.

싸피 들어가면 순열이랑 조합 문제부터 풀었기 때문에 몸이 기억해서 풀었다..

class Solution {
    public static int[] arr;
    public static List<List<Integer>> result;

    public List<List<Integer>> permute(int[] nums) {
        boolean[] inserted = new boolean[nums.length];
        arr = new int[nums.length];
        result = new ArrayList<>();
        permutation(0, nums, inserted);
        
        return result;
    }
    
    public void permutation(int index, int[] nums, boolean[] inserted) {
        
        if (index == nums.length) {
            result.add(changeFormat(arr));
            return;
        }

        for(int i = 0; i < nums.length; i++) {
            if (inserted[i]) continue;
            arr[index] = nums[i];
            inserted[i] = true;
            permutation(index + 1, nums, inserted);
            inserted[i] = false;
        }
    }

    public List<Integer> changeFormat(int[] nums) {
        List<Integer> list = new ArrayList<>();
        
        for (int n : nums) {
            list.add(n);
        }

        return list;
    }
}