[プログラマ]ターゲット番号

📌 質問する

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以下の自然数です.
>>質問の詳細-プログラマー

💡 プール(Java)

class Solution {
	public static int answer=0;

    public int solution(int[] numbers, int target) {
        dfs(0,0,numbers,target);
        return answer;
    }
    
    //DFS 우선탐색 알고리즘 구현
    public static void dfs(int depth,int sum,int[] numbers,int target){
        //마지막 뎁스인지 검사 -> sum이 타깃넘버면 answer값 증가
        if(depth==numbers.length){ 
            if(sum==target){
                answer++;
            }
            return;
        }
        
        boolean doPlus = true;

        do {
            if(doPlus){ //기호 true면 +, false면 -
                sum+=numbers[depth];
            }else {
                sum-=numbers[depth];
            }
            //다음뎁스로 진입
            dfs(depth+1,sum,numbers,target);
            
            if(doPlus){  //마지막 뎁스에서 +했던거 롤백.
                sum-=numbers[depth];
            }else {
                sum+=numbers[depth];
            }
            doPlus = !doPlus;
        } while(!doPlus);
    }

    /**
     * 4 + 1 + 2 + 1 = sum
     * 4 + 1 + 2 - 1 = sum
     * 4 + 1 - 2 + 1 = sum
     * 4 + 1 - 2 - 1 = sum
     * 4 - 1 + 2 + 1 = sum
     * 4 - 1 + 2 - 1= sum
     * 4 - 1 - 2 + 1= sum
     * 4 - 1 - 2 - 1= sum
     * -4 + 1 + 2 + 1 = sum
     * -4 + 1 + 2 - 1 = sum
     * -4 + 1 - 2 + 1 = sum
     * -4 + 1 - 2 - 1 = sum
     * -4 - 1 + 2 + 1 = sum
     * -4 - 1 + 2 - 1= sum
     * -4 - 1 - 2 + 1= sum
     * -4 - 1 - 2 - 1= sum
     */
}

◇DFS、BFS優先度アルゴリズムを学習して実装に適用する必要があり、このアルゴリズムを理解してまとめるのに時間がかかる.コアは、ルートノードから次のブランチに移動する前に、原点に戻ってから他のブランチを参照する前に、すべてのブランチを参照する必要があります.したがって再帰関数は、自身を呼び出すループアルゴリズム形式を有するため使用されます.どのノード(ex)doPlus=trueにアクセスしたかを確認する必要があります.