순열구하기
문제풀이
function solution(m, arr){
let answer=[];
n=arr.length;
let ch=Array.from({length:n}, ()=>0);
let tmp=Array.from({length:m}, ()=>0);;
function DFS(L){
if(L===m) {
answer.push(tmp.slice());
}
else{
for(let i=0; i<n; i++){
if(ch[i]===0){
ch[i]=1;
tmp[L]=arr[i];
DFS(L+1);
ch[i]=0;
}
}
}
}
DFS(0);
return answer;
}
let arr=[3, 6, 9];
console.log(solution(2, arr));
문제접근법
m=2이고, n=3일때의 예시이다.
1. L=m일때 재귀함수를 종료한다.
구하는 숫자가 위에서는 두자리(m=2)이므로 DFS(2)일때 재귀함수를 종료한다.
if(L===m)
-
ch[i]를 확인한다.
ch[i]가 1이면 이미 숫자를 썼다는 뜻이다. 그러므로 ch[i]=0일때만 tmp에 숫자를 추가해준다.
if(ch[i]===0)
-
재귀함수가 끝나고 다시 위층으로 올라갈때(ex. L=2 -> 1) ch[i] = 1 이였던것을 다시 0으로 바꾸어 준다.
ch[i]=0;
Author And Source
이 문제에 관하여(순열구하기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@minho100227/순열구하기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)