Minimum Number Of Software Developers

package pep.Day81;

import java.io.*;
import java.util.*;

public class Minimum_Number_Of_Software_Developers {
    static ArrayList<Integer> sol = new ArrayList<>();

    //nskills -> total number of skills
    // cp -> current person
    // onesol -> solution
    // skills -> a OR b  agr a+b krna hoga
    public static void solution(int[] people, int nskills, int cp, ArrayList<Integer> onesol, int skills) {
        // BASE CASE
        // cp out of range nhi jaana cheye
        if (cp == people.length) {
            if (skills == Math.pow(2, nskills) - 1) {
                //if (skills == (1 << nskills) - 1) {

                // ek ans mil gya hai
                // sol.size() == 0 -> first ans
                // onesol.size() < sol.size() -> better ans mil gya
                if (sol.size() == 0 || onesol.size() < sol.size()) {
                    // sol = onesol; -> this will not work
                    // sol mujhe humesha khale array return krega
                    // jab hum backtracking krte hain toh hum onesol se remove krte hain
                    // sol, onesol ko point krne lagega and hume onesol ko khale kr diya

                    // SOlution: deep copy bnaenge
                    sol = new ArrayList<>(onesol);
                }

            }

            return;
        }
        // write your code here

        // 1. jisme banda aana nhi chahta hai
        // jisme hum skill ko include nhi kr rhe

        // cp+1 islea kiya -> 'a' ne decide kr liya hai ki woh nhi aaega, now check for 'b'
        // onesol
        // skills -> jab 'a' aana hi nhi chahta to uski skills bhi add nhi krnge, toh skills same rhenge
        solution(people, nskills, cp + 1, onesol, skills);

        // 2. agr banda aana chahta hai

        // add krenge currentPerson ke index ko
        onesol.add(cp);

        // kise person ko add kr rhe hain, to hum current person ke skill set se OR kr denge
        solution(people, nskills, cp + 1, onesol, (skills | people[cp]));

        // back tracking ki jrurt padege
        onesol.remove(onesol.size() - 1);


    }

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        HashMap<String, Integer> smap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            smap.put(scn.next(), i);
        }

        int np = scn.nextInt();
        int[] people = new int[np];
        for (int i = 0; i < np; i++) {
            int personSkills = scn.nextInt();
            for (int j = 0; j < personSkills; j++) {
                String skill = scn.next();
                int snum = smap.get(skill);
                people[i] = people[i] | (1 << snum);
            }
        }

        solution(people, n, 0, new ArrayList<>(), 0);
        System.out.println(sol);

    }

}