DFSによる繰返しシーケンスの解析

質問する

入力例

3 2

出力例

1 1
1 2
1 3
2 1
2 2 
2 3
3 1
3 2
3 3
9

に答える

ツリー構造

      		 DFS(0)
               /   ㅣ   \
         DFS(1)  DFS(1)  DFS(1)   
        /  ㅣ  \	/  ㅣ  \	/  ㅣ  \
     DFS(2) ... ... 
    /  ㅣ  \	
 DFS(3) ... ...

function solution(n, m){
  let answer=[];
  let tmp=Array.from({length:m}, ()=>0);
  function DFS(L){
    // 탈출조건
    if(L===m){ // for문으로 작성했다면 m중for문
      //=>tmp를 바로 push하면 같은 주소값을 사용하므로 slice()를 사용해서 push함
      answer.push(tmp.slice());
    } else{
      //1부터 n까지 반복
      for(let i=1; i<=n; i++){ 
        tmp[L]=i;
        DFS(L+1);
      }
    }   
  }
  DFS(0);
  return answer;
}

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

首都コード