Leetcode in Java - 46. Permutations (재귀)

알고리즘 설명

 

재귀함수는 depth라는 정수를 매개변수로 받는데, 이 depth는 재귀적으로 함수를 호출할 때마다 1씩 늘어난다. depth에 따라 swap 해주어야 하는 배열의 인덱스가 달라지기 때문이다. swap 해주어야 하는 두 인덱스는 depth와 i인데, i는 depth부터 시작해 배열의 끝(n-1)까지 증가한다. depth가 n과 같아지면 swap하지 않고 최종 반환할 리스트에 추가한다.

 

코드

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        perm(ans, nums, 0);
        return ans;
    }

    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    public void perm(List<List<Integer>> ans, int[] arr, int depth) {
        int n = arr.length;

        if (depth == n-1) {
            // Arrays.stream(arr).boxed().collect(Collectors.toList())은 for문보다 느림.
            // 이유 : 스트림 연산은 내부적으로 람다식, 함수형 인터페이스, 메서드 참조 등이 발생하기 때문.
            List<Integer> list = new ArrayList<>();
            for (int i=0; i<n; i++) {
                list.add(arr[i]);
            }
            ans.add(list);
            return;
        }
        
        for (int i=depth; i<n; i++) {
            swap(arr, depth, i);
            perm(ans, arr, depth+1);
            swap(arr, depth, i);
        }

        /**
        depth  i    arr      ans
        0      0    [1,2,3]
        1      1    [1,2,3]
        2      2    [1,2,3]  [[1,2,3]]
        1      2    [1,3,2]
        2      2    [1,3,2]  [[1,2,3], [1,3,2]]      
        0      1    [2,1,3]
        1      1    [2,1,3]
        2      2    [2,1,3]  [[1,2,3], [1,3,2], [2,1,3]]
        1      2    [2,3,1]
        2      2    [2,3,1]  [[1,2,3], [1,3,2], [2,1,3], [2,3,1]]
        0      2    [3,2,1]
        1      1    [3,2,1]
        2      2    [3,2,1]  [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1]]
        1      2    [3,1,2]
        2      2    [3,1,2]  [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,2,1], [3,1,2]]
        */
    }
}