[Programmers](ハイスコアKIT)DFS&BFS-ターゲット番号


https://programmers.co.kr/learn/courses/30/lessons/43165
問題の説明
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
使用可能な数値の配列番号、ターゲット番号のターゲットをパラメータとして指定したときに、適切に数値を加算して減算して、ターゲット番号を作成する方法の数を返します.
せいげんじょうけん
与えられた数字の個数は2個または20個以上である.
各数字は1または50以下の自然数です.
ターゲット番号が1または1000以下の自然数です.
I/O例
numberstargetreturn[1, 1, 1, 1, 1]35[4, 1, 2, 1]42
Solution
#include <string>
#include <vector>

using namespace std;

int answer = 0;

void DFS(vector<int> numbers, int target, int sum, int count){
    if(numbers.size() == count){
        if(sum == target) answer++;
        return;
    }
    DFS(numbers, target, sum + numbers[count], count+1);
    DFS(numbers, target, sum - numbers[count], count+1);
}

int solution(vector<int> numbers, int target) {
    DFS(numbers, target, 0, 0);
    return answer;
}
これは,所定の数内にどれだけの目標番号を作成できるかを見出す問題である.
例えば、4,1,2,1では4−1+2−1を用いて4を作成してもよいし、4+1−2+1を用いてもよい.だから2つの方法があると言えます.
これらのものは人が考え出すことができるが、必ずしもそうではない.
int answer = 0;

void DFS(vector<int> numbers, int target, int sum, int count){
    if(numbers.size() == count){
        if(sum == target) answer++;
        return;
    }
    DFS(numbers, target, sum + numbers[count], count+1);
    DFS(numbers, target, sum - numbers[count], count+1);
}
countは、加算回数を格納する変数です.いずれにしても、あらゆる方法を尽くさなければならないので、これらの変数が必要です.まず,無知性ですべての価値を増やした場合と減算した場合を計算する.すべての場合の数を計算する方法はいくつかありますが、DFSを使用する理由は次のとおりです.
それぞれの場合の数はツリー形式で表すことができます.すなわち,これらの木を1つずつ検索する感覚で探索すると,より良い結果が得られる.盲目的にドアを回すのは馬鹿なことをしても構わないが、コードはずっと複雑になる.
したがって,それぞれの場合の数についてDFSをそれぞれ行い,Leaf Nodeに到達したとき(count=numbers.size()に結果を確認する.
探索の方法はいろいろあるが,どのような過程であるかを確認すれば,より高度な探索方法を考えることができる.