LeetCode高频题：dfs排列组合问题，剪枝策略，参观展厅总时间120分钟，请你给出所有可能的参观方案的个数

提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题

---

文章目录

• LeetCode高频题：dfs排列组合问题，剪枝策略，参观展厅总时间120分钟，请你给出所有可能的参观方案的个数
• • @[TOC](文章目录)
• 题目
• 一、审题
• 咱们来审题
• dfs组合各个位置的数？不要它还是要它？加入path累加和，只要path=60就算是一个成功的方案
• 因此我们先手撕A（n，k）咋求？
• 最终确定定义 f（arr,i,tmp） 外加一个全局变量path，方便恢复现场
• 再来看本题，关键是找当捞出多个位置组合恰好为60分钟时，ans记录了我们有几个位置？N-ans就是咱们余下下午120分钟的位置数量
• 总结

题目

某代表团要来参观航天展厅，参考的招聘包含航天的学习飞机，翻译机，扫描笔，AI办公本，阿尔法蛋等众多产品。每个产品参观的时间不完全相同（最小的单位是分钟），但是总时长是3小时，且上午参观一个小时，下午参观2个小那个是。已知参观的展品数为N（每个展品标记为1—N），且每个展品参观的时间分别为M1,M2–MN分钟，那么满足上午参观总时间为60分钟，下午参观总时长为120分钟的条件下，请你给出所有可能的参观方案个数。

输入描述：
第一行输入一个正整数N，表示参展展品数量
第二行输入N个正整数分别为M1,M2,–MN，表示每个展品参展的时间，且他们一定和为180

输出描述：
输出所有满足上午参观总时长为60，下午参观总时长为120的方案个数（正整数），若没有任何方案或者输入不合法，则输出0

---

一、审题

示例：
6
10 20 30 30 40 50
输出
216

---

咱们来审题

其实给你限制M1,M2,–MN他们一定和为180已经是很仁慈了
否则你还得慢慢剪枝

这题，给你一个数组arr，实际上问你，有哪些位置，组合出一个60分钟来？？？
剩下的必然是120，没的说

比如一次能组合出60来的数量有3个
还有5个位置组合是120分钟

那么结果应该是A(3,3)×A(5,5)=720种方案
因为上面3种谁排前面，谁排后面的方案有A(3,3)=6种
下面5种谁排前面，谁排后面的方案有A(5,5)=5×4×3×2=120种
所以总的方案数就是：
6×120=720

如果一直没有组合出60来，绝对没法玩，提前剪枝

整体就是dfs排列组合的事情，我讲过多次了——这都是之前LeetCode上面考过的题目
【1】排列：LeetCode高频题46. 全排列

【2】组合：LeetCode高频题78. 子集，返回该数组所有可能的子集（幂集），生成所有的子序列

本题更像是【2】

dfs组合各个位置的数？不要它还是要它？加入path累加和，只要path=60就算是一个成功的方案

我们定义一个函数f（arr,i,path,ans）
从arr的i–N-1位置，有多少种可能的组合方案，可以让参观时间恰好提前让path=60

来到arr的i位置，决定i不要，还是要？
如果要，就加入path结果，一旦path超过60就让ans+可以组合出的方案数，算是一种合法情况

另外，要提前剪枝：
（1）如果i已经到了arr的N位置，越界了，那说明方法不合法，ans+0，返回0
（2）如果中途path已经超过60了，不好意思，这个方案无效，ans+0，返回0
（3）如果path=60，很OK，ans可以加我们组合的方案了，返回当前情况下的有效组合数
（4）path就还没有超过60，因此可以考虑
【1】不要arri，那直接去i+1位置决定
【2】要arri，将path+arri，然后去i+1位置决定
当然，情况2，是要考虑恢复现场的，一直用同一个path，你需要把刚刚加过的arri，吐出去，这样path才能考虑更多的情况
这个恢复现场的事情，我讲过多次了

上面的（3）中，有了ans，就是组合出60分钟的个数
N-ans就是整体120分钟的个数
a=A（ans，ans）就是60分钟他们随意排序的方案整体数
b=A（N-ans，N-ans）就是120分钟他们随意排序的方案整体数
a×b就是上午下午组合的方案数——这就是当前情况下的有效组合方案数

再举一个例子：
题目给的例子
你给了我arr=10 20 30 30 40 50
第一种：10+50=60，两个位置，剩下的下午看，那就是A(2,2)*A(4,4)=48种组合方案
第二种：20+40=60，两个位置，剩下的下午看，那就是A(2,2)*A(4,4)=48种组合方案
第三种：30+30=60，两个位置，剩下的下午看，那就是A(2,2)*A(4,4)=48种组合方案

第四种：10+20+30=60，3个位置，剩下的下午看，那就是A(3,3)*A(3,3)=36种组合方案
第四种：10+20+30=60【注意，这个30是arr的第2个30哦】，3个位置，剩下的下午看，那就是A(3,3)*A(3,3)=36种组合方案

现在你知道案例中216怎么来的了吧？

你也看到了，咱们需要有一个求A(n,k）的这么一个函数

---

因此我们先手撕A（n，k）咋求？

        //手撕A（n，k）咋求？
        public static int Ank(int n, int k){
            int[] dp = new int[n + 1];//求Ank--0不用
            //公式是n*n-1*--n-k+1

            dp[n - k + 1] = n - k + 1;
            for (int i = n - k + 2; i <= n; i++) {
                dp[i] = dp[i - 1] * i;
            }

            return dp[n];
        }
1
2
3
4
5
6
7
8
9
10
11
12

测试：

        public static void test(){
            System.out.println(Ank(5,1));
            System.out.println(Ank(5,2));
            System.out.println(Ank(5,3));
            System.out.println(Ank(5,4));
            System.out.println(Ank(5,5));
        }
1
2
3
4
5
6
7

5
20
60
120
120
1
2
3
4
5

最终确定定义 f（arr,i,tmp） 外加一个全局变量path，方便恢复现场

和我们上面定义的函数**f（arr,i,path,ans）**没啥区别
从arr的i–N-1位置，有多少种可能的组合方案，可以让参观时间恰好提前让path=60

        //我们定义一个函数**f（arr,i,tmp）**
        //从arr的i--N-1位置，有多少种可能的组合方案，可以让参观时间恰好提前让path=60
        //来到arr的i位置，决定i不要，还是要？
        //如果要，就加入path结果，一旦path超过60就让ans+1，算是一种合法情况
        public static int path = 0;//全局变量，可能变更

        public static int f(int[]arr, int i, LinkedList<Integer> tmp){
            //（1）如果i已经到了arr的N位置，越界了，那说明方法不合法，ans+0，返回0
            if (i == arr.length) {
                //这里要小心，有可能这时候，恰好就path=60，你需要结算，不是pthh=60的话，不要意思，返回0个组合
                //如果path=60，很OK，ans+1，返回当前组合情况下的有效方案数
                if (path == 60) {
                    int N = arr.length;
                    int ans = tmp.size();
                    return Ank(ans, ans) * Ank(N - ans, N - ans);//上午*下午的组合数量
                }
                return 0;//否则不行
            }
            //（2）如果中途path已经超过60了，不好意思，这个方案无效，ans+0，返回0
            if (path > 60) return 0;
            //（3）如果path=60，很OK，ans+1，返回当前组合情况下的有效方案数——中途剪枝
            if (path == 60) {
                int N = arr.length;
                int ans = tmp.size();
                return Ank(ans, ans) * Ank(N - ans, N - ans);//上午*下午的组合数量
            }
            //（4）path就还没有超过60，因此可以考虑
            //【1】不要arri，那直接去i+1位置决定
            int N1 = f(arr, i + 1, tmp);

            //【2】要arri，将path+arri，然后去i+1位置决定，要的话ans就要+1
            path += arr[i];
            tmp.addLast(arr[i]);
            int N2 = f(arr, i + 1, tmp);
            path -= arr[i];//清除现场
            tmp.removeLast();

            return N1 + N2;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

千万小心，那个f，在i==N时，你可要判断path=60与否，是就要算一种结果
否则返回0

中途该剪枝就剪枝，一切OK

再来看本题，关键是找当捞出多个位置组合恰好为60分钟时，ans记录了我们有几个位置？N-ans就是咱们余下下午120分钟的位置数量

而a=A（ans，ans）就是60分钟他们随意排序的方案整体数
b=A（N-ans，N-ans）就是120分钟他们随意排序的方案整体数
a×b就是上午下午组合的方案数

上面说清楚了，手撕代码：

        public static int path = 0;//全局变量，可能变更

        public static void main(String[] args) {
            Scanner in = new Scanner(System.in);

            int N = in.nextInt();//N
            int[] arr = new int[N];
            for (int i = 0; i < N; i++) {
                arr[i] = in.nextInt();
            }

            LinkedList<Integer> tmp = new LinkedList<>();///中途哪些加入path了？
            int all = f(arr, 0, tmp);//一个方案没有，看看你能得到多少？
            System.out.println(all);

        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

测试：
6
10 20 30 30 40 50

结果：216

美滋滋，绝对美滋滋，就是一个组合，中途要判断你加入tmp的所有元素和path是否为60？
是咱就要结算上午下午的组合数，返回

刺激！！！

尤其是i==N那，可一定要结算，否则就少了

---

总结

提示：重要经验：

1）dfs剪枝，经常考，经常写，就是LeetCode高频题里面的东西
2）自己多敲代码，手撕熟悉了，解决问题就不难了
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。