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

1240 ワード
プログラマ アルゴリズム#アルゴリズム# テキストリンク

問題の説明


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例

numbers		target	return
[1, 1, 1, 1, 1]	  3	  5

私の答え

import java.util.*;

class Solution {
    public int solution(int[] numbers, int target) {

        int answer = dfs(numbers,0,0,target);

        return answer;
    }
    
    public static int dfs(int []numbers,int depth,int sum,int target) {
      if(depth == numbers.length){
          if(sum == target) return 1;
          else return 0;
      }else{
          return dfs(numbers,depth+1,sum+numbers[depth],target) + dfs(numbers,depth+1,sum-numbers[depth],target);  
        }
    }
}
dfs問題はdepthとsumを0に設定し、パラメータに渡します.
深さに数を足す.値がlengthと同じ場合、1を返します.
そうでない場合は0を返します.
[Java] - Method References
docker-pyで docker daemonを遠隔操作してみようのコーナー