[DFS][JS]繰り返しシーケンス

4191 ワード

質問する


1からNと書かれたビーズがあります.M番号を繰り返し抽出して1列に列挙できるすべてのメソッドを出力します.
■説明の入力
第1行は、自然数N(3<=N<=10)およびM(2<=M<=N)を与える.
■出力説明
最後の合計を出力します.
■入力例3 2
出力例9
##解答
入力
順番が違うと違う組み合わせを使います.
したがって,我々は繰り返す必要はなく,1,2,3を迂回して2つの組合せを完成させるだけでよい.
function solution(n, m) {
  const ch = Array.from({length:m}, () => 0)
  let level = 0;
  let answer = [];
  
  function dfs(level) {
		if(level === m) {
      answer.push(ch.slice())
    }
    else {
			for(let i = 1; i<=n; i++) {
        ch[level] = i
        dfs(level + 1)
      }
    }
  }
  dfs(0)
  return answer.length;
}

solution(3, 2) //9
デップに入るごとに差し伸べられた義肢が1,2,3種類あるため,forゲートの周りを再帰的に呼ぶ.経過した数字を覚えて、組み合わせで表すのでch配列に入れます.
デップスレベルが2つになれば、保存されている2つの数字を出せばいい.

Reference

  • JavaScriptアルゴリズム回答-インフラストラクチャ