수들의 조합

문제 풀이 원리

문제 예와 같이 arr = [2, 4, 5, 8, 12]라면 첫번째 자리수가 2일때의 결과물이다.
두번째 층에서 세번째 층으로 내려갈때 4가 제일 많고 12는 하나도 없는 것을 알 수 있다.
즉, 숫자가 중복되면 안되므로 이전에 나온 수는 쓰지 않게 해야한다.

function solution(n, k, arr, m){         
        let answer=0;
        function DFS(L, s, sum){
            if(L === k){
                if(sum%m===0) answer++;
            }
            else{
                for(let i=s; i<n; i++){
                    DFS(L+1, i+1, sum+(arr[i]));                            
                }
            }
        }
        DFS(0,0,0);
        return answer;
    }

    let arr=[2, 4, 5, 8, 12];
    console.log(solution(5, 3, arr, 6));

여기서 핵심은 아래와 같다.

for(let i=s; i<n; i++){
     DFS(L+1, i+1, sum+(arr[i]));                            
}

이렇게 i를 s로 정해주면 이전에 썼던 수는 쓸수가 없다.

예를들어 DFS(1,1,2)로 시작해 끝까지 다 완료한 후에 DFS(1,1,2)가 끝나면 반복문에 의해 i++가 되어 i=2가 되므로 DFS(1,2,4)가 시작된다.
즉, DFS(1,2,4)부터는 i=1을 쓸 수 없다.