蓝桥杯算法训练VIP-和为T-题解-经典部分和问题的变体（Java代码）

解题思路:使用深搜方法，其实我们每次都是在考虑当前的数要或者不要两种情况，那么就是每次深搜下探延伸出两条支线。

参考代码:

//经典部分和问题的变体
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		int[] arr = new int[n];
		for(int i = 0; i < n; i++)
		{
			arr[i] = in.nextInt();
		}
		K = in.nextInt();
		dfs(arr, 0, n - 1);
		System.out.println(cnt);
		
		in.close();
	}
	
	public static int n;	//几个数字
	public static int K;  //要求的和
	public static int cnt = 0;
	public static ArrayList<Integer> list = new ArrayList<>();	//存放选入的数字
	
	/*
	 * arr 待选数组
	 * k   目前已有和
	 * cur 目前决定第几个数字的选取
	 */
	public static void dfs(int[] arr, int k, int cur) {
		if(cur == -1)
		{
			if(list.size() != 0)
			{
				if(k == K)
				{
					cnt++;
					for(int i = list.size() - 1; i >= 0; i--)
					{
						System.out.print(list.get(i));
						if(i != 0)
						{
							System.out.print(" ");
						}
					}
					System.out.println();
				}
			}
			return;
		}
		
		//不选cur
		dfs(arr, k, cur - 1);
		
		//选cur
		list.add(arr[cur]);
		dfs(arr, k + arr[cur], cur - 1);
		list.remove(list.size() - 1);	//回溯
	}
}