プログラマ>DFS/BFS>ターゲット番号
https://programmers.co.kr/learn/courses/30/lessons/43165?language=java

質問する

n個の非負の整数がある.順序を変更せずにこれらの整数を適切に追加または減算してターゲット番号を作成したいと思います.たとえば、[1,1,1,1,1,1]で数値3を作成するには、次の5つの方法があります.

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.

せいげんじょうけん

で与えられた数字は20個未満です.

各数字

は50より大きい自然数である.

目標は自然数が1000より大きいことです.

I/O例

numberstargetreturn[1, 1, 1, 1, 1]35[4, 1, 2, 1]42

考える

この言葉がネットワークであることを簡単に理解すれば、メインラインに移動できるノードは1であり、別々のノードも1であり、すべて加算すればよい.computers[][]アレイは2次元アレイであるが、実際には自分を境界とする場合、
下も上も、片方だけ見ればいいです.
したがって、visit[]アレイは、computers.lengthの長さの1次元アレイを生成することができる.

DFS

再帰を利用して実現した.
+と-の組み合わせなので、2つの組み合わせだけで構成されています.indexどうせ数字は積み重ねられていて、記号だけが変わります.indexは+1を変更しません.
以下、sumにおいて+と-を区別するためのsum + numbers[index] sum - numbers[index]、二つに分かればいいです.
これで、復帰して、数字ごとに+-を組み合わせることができます.targetのように、answerが増加する.
必要な値を出力できます.
脱出条件はnumbers配列を超えてはならないので、indexの値をnumbers配列の長さと等しく設定した場合に戻る.

TMI

内容は複雑ではないが、2番目から復帰した人材はいつも頭が複雑だ.
手で直接使うのが最高!

コード#コード#

DFSの使用

class Solution {
	static int numbers[];
	static int target;
	static int answer = 0;
	static int length;

    public int solution(int[] numbers, int target) {
    	this.numbers = numbers;
    	this.target = target;
    	this.length = numbers.length;

    	DFS(0, 0);

        return answer;
    }

    static void DFS(int index, int sum) {
    	// 탈출 조건
    	if(index == length) {
    		if(sum == target) answer++; 
    		return;
    	}

    	// 수행 동작
    	DFS(index + 1, sum + numbers[index]);
    	DFS(index + 1, sum - numbers[index]);  
    }
}