46. Permutation

문제정보

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

정수로 이루어진 배열이 주어집니다.
배열의 순열을 모두 담은 2차원 배열을 리턴합니다.

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

정수로 이루어진 배열이 주어지고 그에대한 순열을 구하면 되는 문제입니다.
조건 자체는 굉장히 심플한데 제한사항을 보면
nums.length가 1 <= nums.length <=6네요

단순히 for문을 중첩시켜서 푸는 방식으로는 문제가 있을 것 같습니다.

재귀적인 방법을 통해 푸는 게 깔끔하겠네요

나의풀이(가 아닌 유튜버의 풀이)

아직 재귀를 코드로 구현하기엔 벅차고
코드를 이해하는 수준까지밖에 오지 못했습니다.
그런고로 풀이를... 이해만 해봤습니다.

var permute = function(nums, permutation = [], answer = []) {
    
    if(nums.length === 0) {
        answer.push([...permutation]);
    } // 재귀의 종료조건 꼬리재귀 형태로 구현
     
    for(let i = 0; i < nums.length; i++) {
        permutation.push(nums[i]);
        const choices = nums.filter((num, index) => index !== i);
        permute(choices, permutation, answer) // 재귀함수 호출
        permutation.pop();
    }

    return answer //재귀 종료 후 답 return
};

아주아주아주 자세한 설명은 제 네이버블로그에 있습니다.
https://blog.naver.com/cardiba/222923846408

그러니 자세한 설명이 필요하다면 블로그를 참고해보시고요...

간단하게 설명하면 filter()를 이용해 nums.length를 1씩 줄여나가고
nums.length가 0에 도달하면 꼬리재귀형태로 답을 반환하게끔하는 코드입니다.

굉장히 심플한데
만약에 재귀가 끝나고 permutation을 pop()해주지않으면
이전 재귀가 코드에 계속 남아버리는 문제가 있습니다.

코드의 진행 과정을 nums가 [1,2,3]인 케이스에서 보면

[1] -> [1,2] -> [1,2,3] -> [[1,2,3]] -> [1,2] -> [1] -> [1,3] -> [1,3,2] -> [[1,2,3][1,3,2]]

이런식으로 코드가 진행됩니다.
하나하나 console.log()를 찍어보면서 코드 동작 흐름을 보시면 이해가 빠를거에요

var permute = function(nums, permutation = [], answer = []) {
    
    if(nums.length === 0) {
        answer.push(...permutation);
    }
    
    for(let i = 0; i < nums.length; i++) {
        permutation.push(nums[i]);
        console.log("push시점 permutation" + permutation);
        const choices = nums.filter((num, index) => index !== i);
        console.log("choices 상태" + choices);
        permute(choices, permutation, answer);
        permutation.pop(); 
        console.log("pop된 상태" + permutation);
    }
    return answer
};

제 경우에는 이런식으로 push시점 , choices 상태, pop된 상태를 각각 console.log로
찍어보면서 이해를 해봤습니다.

push시점 permutation1
choices 상태2,3
push시점 permutation1,2
choices 상태3
push시점 permutation1,2,3
choices 상태
pop된 상태1,2
pop된 상태1
push시점 permutation1,3
choices 상태2
push시점 permutation1,3,2
choices 상태
pop된 상태1,3
pop된 상태1
pop된 상태
push시점 permutation2
choices 상태1,3
push시점 permutation2,1
choices 상태3
push시점 permutation2,1,3
choices 상태
pop된 상태2,1
pop된 상태2
push시점 permutation2,3
choices 상태1
push시점 permutation2,3,1
choices 상태
pop된 상태2,3
pop된 상태2
pop된 상태
push시점 permutation3
choices 상태1,2
push시점 permutation3,1
choices 상태2
push시점 permutation3,1,2
choices 상태
pop된 상태3,1
pop된 상태3
push시점 permutation3,2
choices 상태1
push시점 permutation3,2,1
choices 상태
pop된 상태3,2
pop된 상태3
pop된 상태

좀 어지러울 수 있지만 하나하나 읽어보시다보면
재귀구조여서 어렵게 느껴지는거지
코드 자체가 난해한건 아니라는 생각이 들거에요!!