招行卡第二题求大佬指点思路一波

package coding_test;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Zhaoyin2 {
    public static void main(String[] args) {
        //给定一个String，可以添加加减号，使得该Stringd的值等于k，求方案又多少中
        Scanner scanner = new Scanner(System.in);

        int num = scanner.nextInt();
        scanner.nextLine();

        Map<String,String> map = new HashMap<>();
        int index = 0;
        while(index < num){
            String key = scanner.nextLine();
            String value = scanner.nextLine();
            map.put(key,value);
            index++;
        }

        for(String key: map.keySet()){
            System.out.println(countNumber(key,Integer.valueOf(map.get(key))));
        }



    }

    public static int countNumber(String target,int num){
        char[] charArr = target.toCharArray();
        int [] intArr = new int[target.length()];
        for(int i = 0 ; i < target.length() ; i++){
            intArr[i] = charArr[i]-48;
        }

        int [][] dpArr = new int[target.length()][(int)Math.pow(2,target.length()-1)];
        dpArr[0][0] = intArr[0];
        for(int i = 1 ; i < target.length();i++){
            for(int j = 0 ; j < 2*i;){
                for(int k = 0; k < (int)Math.pow(2,(i-1));k++){
                    dpArr[i][j++] = dpArr[i-1][k]+intArr[i];
                    dpArr[i][j++] = dpArr[i-1][k]-intArr[i];
                }
            }
        }
        int count = 0 ;
        for(int i = 0 ; i < (int)Math.pow(2,target.length()-1);i++){
            if(dpArr[target.length()-1][i] == num){
                count++;
            }
        }
        return count;
    }
}