LeetCode: 46번 (Permutations) [JAVA]

문제 링크

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

Permutations - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

1. 순열 순서 저장용 arr 생성 (모든 원소 -1로 초기화)
2. 순열 생성 함수 생성
   1) 파라미터 - nums 배열, nums 배열에 대한 인덱스(index), arr 배열
   2) index가 nums 배열 길이가 되면 순열 생성이 완료된 것으로 해당 List를 만들어 답에 추가
   3) for문을 통해 전체 arr 배열을 돌며 원소가 -1인 곳이 생기면 해당 곳에 index를 삽입 후 다음 함수 호출
   4) 이후 해당 위치를 다시 -1로 초기화(백트래킹)
3. 결과 List<List<Integer>> 반환

 단순한 순열 생성 문제이다. 자바에서는 순열, 조합을 생성해주는 라이브러리가 없다보니 직접 구현해야 하는데, 백트래킹 기반으로 구현을 할 수 있다. 우선 순열 순서를 임시 저장할 배열(arr)을 생성해주고, 모든 원소를 -1로 초기화를 해준다. 그 다음엔 순열 생성 함수를 구현하는데, 전체적인 구조는 백트래킹 기반이다. 파라미터로는 nums 배열, nums 배열에 대한 인덱스, arr 배열이고, 해당 함수의 기저 조건은 index가 nums 길이만큼 도달했을 때 임시 저장용 arr 속 값들을 가져와 순열 List를 만들어 답에 추가하는 방식이다. 탐색의 경우 for문을 통해 전체 arr 배열을 돌며 원소가 -1인 곳이 생기면 해당 곳에 index를 삽입 후 다음 함수 호출하고, 이후 해당 위치를 다시 -1로 초기화를 해 다른 nums 원소가 해당 자리에 올 수 있도록 한다.
 이후 해당 순열 생성 함수를 호출한 다음, 결과가 저장된 List<List<Integer>>을 반환하면 된다.

 

class Solution {
    List<List<Integer>> result = new ArrayList<>();//리턴용 답안 배열
    public List<List<Integer>> permute(int[] nums) {
        int[] arr = new int[nums.length];
        Arrays.fill(arr, -1);
        permutation(nums, 0, arr);
        return result;
    }

    void permutation(int[] nums, int index, int[] arr) {//순열 생성
        if (index == nums.length) {//nums 배열 모두 사용했으면
            List<Integer> set = new ArrayList<>();

            for (int i = 0; i < arr.length; i++) {//해당 순열 List 생성
                set.add(nums[arr[i]]);
            }

            result.add(set);//답에 추가
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {//배열의 빈 곳이면
                arr[i] = index;
                permutation(nums, index + 1, arr);
                arr[i] = -1;//백트래킹을 위해 다시 빈 곳으로 표시
            }
        }
    }
}

결과