조합구하기

문제풀이원리

문제의 핵심은 인자가 중복되면 안된다는 것이다.
즉 (1,4)가 있으면 (4,1)은 안된다.
이를 위해서 DFS(L,s)에서 s의 값을 +1해주어 이전에 했던 숫자는 다시 사용하지 못하도록 한다.
코드를 보며 더 자세히 살펴보자

function solution(n, m){         
        let answer=[];
        let tmp=Array.from({length:m}, ()=>0);;
        function DFS(L, s){
            if(L===m){
                answer.push(tmp.slice()); 
            }
            else{
                for(let i=s; i<=n; i++){
                    tmp[L]=i;
                    DFS(L+1, i+1);
                }
            }
        }
        DFS(0, 1);
        console.log(tmp);
        return answer;
        
    }

    console.log(solution(4, 2));

else구문에서 i의 값을 s로 지정한다.
즉, i의 값이 반복문으로 인해 +1된다.
또한 재귀함수에서 DFS(L+1, i+1)이므로 결국 다음 재귀함수는 기존의 s+1부터 시작하므로 이전 숫자는 사용하지 않게 된다.

헷갈렸던점

마지막 4는 어떻게 되는가?
마지막 쯤 가면 (3,4)가 나와있어 p[0]이 4일때는 아무일도 일어나서는 안된다.
즉, DFS(0,4)는 어떤 일이 일어날까?
먼저 DFS(0,4)가 일어나기 전에 tmp=[3,4]이다.
이 결과 i=4가되고 tmp[0]=4이므로 [4,4]가 된다. 그리고 DFS(1,5)가 실행된다.
DFS(1,5)가 실행되면 i<=n이므로 n은 4이다.
즉, s>n보다 크므로 DFS(1,5)는 맞는 조건이 없으므로 그대로 종료된다.