题解 | #百钱买百鸡问题#

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int a = in.nextInt();
            int[] arr =  {1, 3, 5}; // 转化为 5,3,1组合问题。由于鸡仔只能三只卖，所以最后结果算数量还要处理
            ArrayList<List<Integer>> results = new ArrayList();
            LinkedList<Integer> path = new LinkedList();
            backTrace(results, path, arr, 0, 0);
            for (int i = results.size() - 1; i >= 0 ; i--) { // 测试要求结果有顺序，所以只能倒着遍历
                List<Integer> list = results.get(i);
                    for (Integer num : list) {
                        System.out.print(num + " ");
                    }
                    System.out.println();
            }
        }
    }

    private static void backTrace(ArrayList<List<Integer>> results,LinkedList<Integer> path, int [] arr, int sum, int startIndex) {
        if (sum > 100) {
            return;
        }

        if (sum == 100) { // 当和为100，需要把结果记录进去
            int male = 0, female = 0, child = 0;
            for (Integer num : path) {
                if (num == 5) {
                    male++;
                } else if (num == 3) {
                    female++;
                } else {
                    child++;
                }
            }
            LinkedList<Integer> list = new LinkedList();
            if(male+female+child*3 == 100) { //同时要求三种鸡数量为100
                list.add(male);
                list.add(female);
                list.add(child * 3);
                results.add(list);
            }// 把各种鸡数量组成一个集合，加入结果集中
             
        }

        for (int i = startIndex; i < arr.length ; i++) {
            if (sum + arr[i] > 100) {
                break; // 减枝
            }
            sum = sum + arr[i];
            path.add(arr[i]);
            backTrace(results, path, arr, sum, i);
            sum = sum - arr[i]; // 回溯撤销
            path.removeLast(); // 回溯撤销路径
        }
    }
}