当时没做出来，心有余悸，害~~~

题目

一家公司有员工worker[1,2,3,4]，每个员工都有一个自己熟悉的技术skill[a,a,b,c]

注意：一个员工对应一个技术

现在将员工分一个小组出来，要求这个小组内的员工对应的技术有n种。

问：共有多少种分法？

如：worker[1,2,3,4]，skill[a,a,b,c]，n = 3

共有 3 种：

分别是： [1,3,4], [2,3,4], [1,2,3,4]

解析

处理数据，保存每种技术对应的人有多少个，如skill[a,a,b,c] => {{a,2},{b,1},{c,1}};

排列组合取出n组数出来，比如当n = 3时，取出来[2,1,1]。然后对[2,1,1]按公式求 $(2^2-1)\ast (2^1-1)\ast (2^1-1)(2^2\; -\; 1)\; *\; (2\; ^\; 1\; -\; 1)\; *\; (2\; ^\; 1\; -\; 1)$ ，可以发现我们是对[2,1,1]种每一个数求 $2^x-12^x\; -\; 1$ 并累积（x属于[2,1,1]），求出的结果累加到返回值。

把每一种排列组合累积的结果相加就是最后的结果了。

代码

package demo;

import org.junit.Test;
import sun.awt.windows.ThemeReader;

import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.LockSupport;
import java.util.concurrent.locks.ReentrantLock;
import java.util.stream.Collectors;

public class Demo {
    int res = 0;
    int[] ns;

    /**
     * 干事的方法
     * @param ss 各项技术
     * @param n 一组技术种数
     */
    int f(String[] ss, int n){
        ns = new int[n];
        Map<String, Integer> map = new HashMap<>();
        for(String str : ss){
            map.put(str, map.getOrDefault(str, 0) + 1);
        }

        List<Integer> list = new ArrayList<>(map.values());
        dfs(list, 0, 0);

        return res;
    }

    // 深度优先，”枚举“出所有排列组合
    private void dfs(List<Integer> list, int index, int floor) {
        if(floor == ns.length) {
            res += calc(ns);
            return;
        }
        for(int i = index; i < list.size(); i++){
            ns[floor] = list.get(i);
            dfs(list, i + 1, floor + 1);
        }
    }

    // 按照公式累积
    int calc(int[] ns){
        int res = 1;
        for(int i : ns){
            res *= (1 << i) - 1;
        }

        return  res;
    }

    @Test
    public void r1(){
        String[] ss = {"a","a","b","d"}; // 各项技术
        System.out.println(f(ss, 3));
    }
}