순열구하기

6917 단어 DFS재귀함수DFS

문제풀이

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)

  1. ch[i]를 확인한다.

    ch[i]가 1이면 이미 숫자를 썼다는 뜻이다. 그러므로 ch[i]=0일때만 tmp에 숫자를 추가해준다.

    if(ch[i]===0)

  2. 재귀함수가 끝나고 다시 위층으로 올라갈때(ex. L=2 -> 1) ch[i] = 1 이였던것을 다시 0으로 바꾸어 준다.

    ch[i]=0;

    	

좋은 웹페이지 즐겨찾기