[Medium] 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]]

 

제약 조건

Constraints:

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• All the integers of nums are unique.

 

풀이 과정

 

제로베이스 JavaScript 알고리즘 강의 중 순열 강의를 참고했다.

최대한 결합도을 낮추려고 했지만 그 과정 중 자꾸 Error가 나서 재귀 흐름 중간에 result.push()를 해주었다. 

개인적으로 순열 재귀 흐름은 코드의 흐름대로 이해하는 것보다 재귀 함수 호출을 stack에 쌓은 다음 호출하는 곳으로 이동하지 않고 일단 일반 코드 흐름을 따라간 다음, 재귀 호출을 따로 해서 계산하는 것이 더 이해하는 데에 수월했다.

• 인자를 배열, 시작 인덱스, 뽑을 개수(0-start)를 받는 permutation()를 호출한다.
• arr[s]의 자리가 고정되면, 첫번째 요소에 대한 순열만 구해지기 때문에 arr[s]의 자리를 swap 해준다.
  • 첫번째 재귀문일 때는 arr[s]가 첫번째 요소, 두번째 재귀문일 때는 arr[s]가 두번째 요소가 된다. 
  •  swap을 한 후, 다시 원상복귀 시킨다.
• permutaition()을 재귀 호출한다. 이때, 인자는 arr, s+1, r를 넘긴다. s + 1 은 '첫번째 요소를 선택했으니까 두번째 요소를 선택해!' 라는 의미이다.

Example 1를 예시로 들어보겠다.

s = 0, r = 2, i = 0 [ 1, ]

s = 1, r = 2, i = 1 [1, 2, ]

s = 2, r = 2 [1, 2, 3]

...

s = 1, r = 2, i = 2 [1, 3, ]

s = 2, r = 2, [1, 3, 2]

s = 1, r = 2, i = 2 [1, 2, ]

...

s = 0, r = 2, i = 1 [ 2, 1, 3]

s

..

s = 0, r = 2, i = 2 [1, ]

 

풀이 코드

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let result = [];
    
    const permutation = (arr, s, r) => {
        let ret = [];
        // 1. 재귀 함수를 멈춰야 할 조건
        if(s === r){
            for(let i = 0 ; i < arr.length ; i++){
                ret.push(arr[i]);
            }
            result.push(ret);
            return;
        }
        
        // s= 1
        // 2. 재귀를 돌면서 변경되어야 될 부분 / 메인 로직
        for(let i = s ; i <arr.length; i++){
            [arr[s], arr[i]] = [arr[i], arr[s]];
            permutation(arr, s + 1, r);
            [arr[i], arr[s]] = [arr[s], arr[i]];
        }
    }
    
    permutation(nums, 0, nums.length - 1);
    return result;
};

 

제로베이스에서 순열 재귀를 처음 보았을 때 이해가 가지 않아 하루를 꼬박 코드에 눈을 박고 있었는데, 지금은 다시 보니 바로 이해가 됐다. 알고리즘 문제를 꾸준히 푼 노력이 이렇게 빛을 보는 구나 싶었다.