本文共 2014 字，大约阅读时间需要 6 分钟。

题目

挑选卡片（Picking cards）

链接： https://ac.nowcoder.com/acm/contest/3286/D

牛牛有N张卡片,在第i(1 ≤ i ≤ N)张卡片上写着一个数字xi 。

牛牛现在准备从这些卡片中挑选一些卡片(数量大于等于1)，使得被挑选的这些卡片的数字的平均值为A。 牛牛想问你一共有多少种挑选方法？

输入描述:

输入包括两行。 第一行1个正整数N(1≤N≤50)。 第二行N个整数x i(1≤x i ≤50)。 输出描述: 输出一个整数，表示挑选的方法数。

示例1

输入87 9 8 9输出5说明一共有5种挑选方法使得平均数为8:1、选择第三张卡片2、选择第一、二张卡片3、选择第一、四张卡片4、选择第一、二、三张卡片5、选择第一、三、四张卡片

示例2

输入53 6 2 8 7 6 5 9输出19

dfs深度优先解法

解题思路：

1. 对数组升序排序；
2. 回溯每个数组的每个数，要么选择，要么不选择(list.remove(list.size() - 1);)
3. 当平均值为target，并且余数为0时，加入结果集合中。
4. 结果就是集合的个数。

package backtracking;import java.util.ArrayList;import java.util.Arrays;import java.util.List;// https://ac.nowcoder.com/acm/contest/3286/Dpublic class PickupCards {
     public static void main(String[] args) {
       PickupCards obj = new PickupCards();    //int[] inputs = {7, 9, 8, 9};    //int target = 8;    int[] inputs = {
   3, 6, 2, 8, 7, 6, 5, 9};    int target = 5;    int result = obj.pickupCards(inputs, target);    System.out.println("result > " + result);  }  public int pickupCards(int[] inputs, int target) {
       // check edges    if (inputs == null || inputs.length == 0) {
         return 0;    }    List
   
    
     > resultList = new ArrayList
     
      
       >();    Arrays.sort(inputs);    List
       
         list = new ArrayList
        
         (); //dfs dfs(inputs, resultList, list, 0, target); return resultList.size(); } private void dfs(int[] inputs, List
         
          
           > resultList, List
           
             list, int start, int target) { // exit condition long sum = 0; for (int item: list) { sum += item; } if (list.size() != 0 && sum / list.size() == target && sum % list.size() == 0) { System.out.println(Arrays.toString(list.toArray())); resultList.add(new ArrayList
            
             (list)); return; } if (start >= inputs.length) { return; } list.add(inputs[start]); dfs(inputs, resultList, list, start + 1, target); list.remove(list.size() - 1); dfs(inputs, resultList, list, start + 1, target); }}
            
           
          
         
        
       
      
     
    
   

代码下载

https://github.com/zgpeace/awesome-java-leetcode/blob/master/code/LeetCode/src/backtracking/PickupCards.java

转载地址：http://ilazk.baihongyu.com/