LeetCode 46. Permutations

순열 만들기

 

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라.

Given an array nums of distinct integers, return all the possible permutations.
You can return the answer in any order.

 

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

---

순열이 만들어지는 것에 대해 먼저 이해할 필요가 있다.

 요소가 3개 일때 순열의 수는 3! / (3 - 3)! 이다. 이중 분모는 1이니, 3 팩토리얼 만큼의 수가 3개의 요소가 주어졌을 때 순열의 총개수이다. 따라서 순열의 수는 '3 * 2 * 1'의 값인 6 이다. 6개의 순열을 생성하기 위해 가장 초기값을 생성 할때는 3개의 요소를 모두 사용한다.

[[1], [2], [3]]. 다음 각 요소로 부터 1개를 제외한 2개씩의 요소를 사용한다. [[1,2], [1,3], [2,1], [2,3], [3,1], [3,2]]. 마지막으로 남은 1개의 요소를 사용하여 순열의 생성을 완성한다. [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]].

 

 위 그래프에서는 아래로 내려갈 수록 자식의 노드가 1개씩 줄어든다. root에서는 자식 노드가 3개, [1, 2, 3]각 노드의 자식 노드는 2개 마지막으로 [1,2] [1,3]과 같은 노드들의 자식노드는 1개이다. 위 순열 수식에 대한 설명과 노드가 줄어드는 모습은 정확히 일치한다. 3 * 2 * 1. 이를 이용해 dfs method를 구현해야 한다.

import java.util.*;

public class Permutations {

    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        List<Integer> elems = Arrays.stream(nums).boxed().toList();

        dfs(results, new ArrayList<>(), elems);

        return results;
    }

    public void dfs(List<List<Integer>> results, List<Integer> prevElements, List<Integer> elements) {
        // 레벨이 증가할수록 자식 노드의 개수가 점점 적어진다.
        // 자식 노드의 개수가 줄어들어 isEmpty() 가 true 로 되면,
        // result 에 지금까지 누적한 값을 List 형태로 add()를 실행한다.
        System.out.println("current prevElements: " + prevElements);
        if (elements.isEmpty()) results.add(new ArrayList<>(prevElements));

        for (Integer e : elements) {
            List<Integer> nextElements = new ArrayList<>(elements);
            nextElements.remove(e);
            prevElements.add(e);
            System.out.println("add e: " + e);
            dfs(results, prevElements, nextElements);
            prevElements.remove(e);
            System.out.println("remove e: " + e);
        }
    }
}

 

위 구현된 코드에서 for 문, 재귀의 동작되는 순서를 그림으로 살펴보자.

 

 

 순열의 생성은 아래와 같이 진행된다.

prevElements에 순열이 완성되고 dfs의 3번째 인자인 elements가 비면, prevElements 값을 results에 더한다.

위 그림에서 순열의 생성은 방향을 지시하는 선의 색상이 이어진 순서대로 진행된다. [1,2,3] 을 추가하고 [1,3,2]를 추가하고 [2,1,3]을 추가한다. 순열 생성은 [3,2,1] 을 추가할때까지 계속 반복되며 진행된다.

 

results에 더한 이후 dfs 함수는 종료되고 상위 재귀함수로 돌아간다. 그림에서 가장 위에있는 prevElements가 비어있는 상태는 dfs메서드가 가장 먼저 실행된 때 이다. 이때를 dfs[1]이라 한다. 이후 for문 안에서 dfs 재귀가 한번 호출됐을 때를 dfs[2]라 한다.

재귀는 총 4단계에 걸쳐 실행되며, Level3 가 됐을 때 results.add()를 실행한다. dfs[1] -> dfs[2] -> dfs[3] ->  dfs[4]( results.add(new ArrayList<>(prevElements)); )

 

 첫 results.add() 동작 이후 재귀가 완료된 후에는 prevElements.remove(e); 가 연달아 실행된다. 이후 dfs[2] 재귀에서 for문에 다음 요소 차례가 실행된다(Integer e = 3). 그리고 [1,3,2]를 추가하는 과정이 진행된다. 그래프를 순회하는 과정을 직관적으로 확인하기 위해 print구문을 담아뒀다.(디버깅을 통해 확인하기에는 재귀로 인해 헷갈린다.) 출력된 결과를 보고 그래프 순회과정을 유추해보자.