算法：结对编程数量

一、题目 §

题目：
某部门计划通过结队编程来进行项目开发，已知该部门有 N 名员工，每个员工有独一无二的职级，每三个员工形成一个小组进行结队编程，结队分组规则如下：
从部门中选出序号分别为 i、j、k 的3名员工，他们的职级分贝为 level[i]，level[j]，level[k]，结队小组满足 level[i] < level[j] < level[k] 或者 level[i] > level[j] > level[k]。其中 0 ≤ i < j < k < n。
请你按上述条件计算可能组合的小组数量。同一员工可以参加多个小组。

输入：
第一行输入：员工总数 n
第二行输入：按序号依次排列的员工的职级 level，中间用空格隔开
限制：
1 ≤ n ≤ 6000
1 ≤ level[i] ≤ 10^5
例子：
4
1 2 3 4

输出：
可能结队的小组数量
例子：
4

二、题解 §

题目看起来有点复杂，理解了其实就是一个 n 个数中取 k 个数的组合数问题。level[i] < level[j] < level[k]和 level[i] > level[j] > level[k] 其实是一个。 组合数就是套回溯模板了。

package org.stone.study.algo.ex202411;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
 
public class PairProgrammingNum {
 
    public static void main(String[] args) {
        int n = 4;
        int[] arr = new int[] {1, 2, 3, 4};
 
        int ans = pairProgrammingNum(n, arr, 3);
        System.out.println(ans);
    }
 
    /**
     * 从 n 个数中选 3 个数
     * @param n：一共 n 个数
     * @param arr
     * @param k：选 3 个数
     * @return
     */
    public static int pairProgrammingNum(int n, int[] arr, int k) {
        List<List<Integer>> ans = new LinkedList<>();
        List<Integer> temp = new LinkedList<>();
 
        backtrack(arr, 0, temp, ans, k);
 
        System.out.println(ans);
        return ans.size();
    }
 
    /**
     * 回溯法求所有组合
     * @param arr
     * @param start
     * @param temp
     * @param ans
     * @param k
     */
    public static void backtrack(int[] arr, int start, List<Integer> temp, List<List<Integer>> ans, int k) {
        if (temp.size() == k) {
            ans.add(new ArrayList<>(temp));
            return;
        }
 
        for (int i = start; i < arr.length; i++) {
            temp.add(arr[i]);
            backtrack(arr, i + 1, temp, ans, k);
            temp.remove(temp.size() - 1);
        }
    }
}