[알고리즘] 순열구하기

문제

10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.

풀이

function solution(m, arr){               
    let answer = '';
    const n = arr.length;
    const visited = new Array(n).fill(0);
    let tmp = new Array(m).fill(0);

    function DFS(L){
        if(L===m){
            answer+=`${tmp}\n`;
            }
            else{
                for(let i = 0; i < n; i++){
                    if(visited[i]===0){
                        visited[i]=1;
                        tmp[L]=arr[i];
                        DFS(L+1);
                        visited[i]=0;
                    }
                }
            }
        }
        DFS(0);
        return answer;
    }
    
let arr =[3, 6, 9];
console.log(solution(2, arr));

• 순열에서는 종료조건 이전까지 for문을 돌며 방문 여부를 체크한다.
• 체크되지 않은 요소는 임시 배열에 넣고, 체크한 뒤 재귀를 호출한다.
• 종료 조건이 되면 출력하고, 재귀가 끝나면 해당 요소는 다시 방문 여부를 해제한다.