趋势科技笔试第二题 简单点说就是深度优先搜索

public class Combination {
    public static int getCombinations(int[] numbers, int target) {
        List<List<Integer>> total = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        if (numbers == null || numbers.length <= 0)
            return -2;
        calculate(total,target,list,numbers);

        if (total == null)
            return -1;
        int length = 0;
        for (List<Integer> result:total)
            length += result.size();
        return length;
    }

    public static void calculate(List<List<Integer>> total, int target,List<Integer> list,int[] numbers){
        if (target == 0){
            ArrayList<Integer> resultList = new ArrayList<>(list);
            if (IsValid(resultList,numbers))
                if (contains(total,resultList) == false)
                    total.add(resultList);
            return;
        }

        int[] a = {1,5,10,20,50,100};

        for (int i=0;i<a.length&&a[i]<=target;i++){
            target -= a[i];
            list.add(a[i]);
            calculate(total,target,list,numbers);
            target += list.get(list.size()-1);
            list.remove(list.size()-1);

        }
    }

    public static boolean IsValid(List<Integer> list, int[] numbers){
        Map<Integer,Integer> map = new HashMap<>();
        int[] a = {1,5,10,20,50,100};
        for (int i=0;i<a.length;i++)
            map.put(a[i],0);

        for (int k:list){
            map.put(k,map.get(k)+1);
        }

        List<Integer> values = new ArrayList<>(map.values());
        for (int i=0;i<numbers.length;i++) {
            if (values.get(i) > numbers[i])
                return false;

        }
        return true;
    }

    public static boolean contains(List<List<Integer>> total, List<Integer> list){
        Collections.sort(list);
        if (total.contains(list))
            return true;
        return false;
    }

    public static void main(String[] args) {
        int numbers[] = {6,5,4,3,2,1};
        int length = Combination.getCombinations(numbers,11);
        System.out.println(length);

    }
}