September 8, 2021

Untitled

<html>
    <head>
        <meta charset="UTF-8">
        <title>출력결과</title>
    </head>
    <body>
        <script>
            function solution(n, f){         
                let answer, flag=0;
                let dy= Array.from(Array(11), () => Array(11).fill(0));
                let ch=Array.from({length:n+1}, ()=>0); //check
                let p=Array.from({length:n}, ()=>0); //순열 저장
                let b=Array.from({length:n}, ()=>0); //조합수 ex)1,3,3,1
              
                const combi = (n,r) => { //조합
                  if(dy[n][r]>0) return dy[n][r];
                  if(n===r || r===0) return 1;
                  else return dy[n][r]=combi(n-1, r-1)+combi(n-1,r);
                }
                
                const DFS = (L, sum) => {
                  if(flag) return;
                  if(L===n && sum===f) { //탈출 조건 sum이 f와 같아야함
                    answer=p.slice();
                    flag=1;
                  } else {
                    for(let i=1; i<=n; i++) {
                      if(ch[i]===0) {
                        ch[i]=1; //있는지 없는지 체크하고
                        p[L]=i; //순열에 넣어준다
                        DFS(L+1, sum+(p[L]*b[L])); //파스칼 삼각형 공식
                        ch[i]=0;
                      }
                    }
                  }
                }
                
                for(let i=0; i<n; i++) {
                  b[i] = combi(n-1, i); //조합수를 미리 저장해둔다
                }
              
               DFS(0,0);
              
                return answer;
            }

            console.log(solution(4, 16));
        </script>
    </body>
</html>