[Java] 1-ms Optimize backtracking solution using 3 techniques
While trying my backtracking solution, I was getting TLE. The optimizations that helped me are shown below:\n\n1. Sort task array in descending order which help
While trying my backtracking solution, I was getting TLE. The optimizations that helped me are shown below:\n\n1. Sort task array in descending order which helps in determining minimum number of sessions in less iterations.\n\n2. Create a global variable that stores the minimum number of sessions possible at any time. Before calling backtracking again, check that number of sessions must be less the the minimum till now. If it is not less than minimum, no need to call backtrack.\n\n3. Do not add a single task to multiple sessions with same timing till now. For example :\n\nSessions=[10,10,0,0,0] 5 sessions with 2 used and 3 unused. \n\nIf we have to add a task with time 3, we do not need to call two backtrack [13,10,0,0,0] and [10,13,0,0,0] by adding in each section, these both give same final answers. Only one is sufficient.\n\n\n```\nclass Solution {\n    // 1st optimization\n    int globe=Integer.MAX_VALUE;\n    \n    public int minSessions(int[] tasks, int sT) {\n        \n        // Sort the given tasks array in ascending order\n        \n        Arrays.sort(tasks);\n        int n=tasks.length;\n        int i=0,j=n-1;\n        while(i<j){\n            int temp=tasks[i];\n            tasks[i]=tasks[j];\n            tasks[j]=temp;\n            i+=1;\n            j-=1;\n        }\n        \n        // create an array for maxium no. of sessions possible\n        \n        int[] session=new int[tasks.length+1];\n        \n        // call backtrack function\n        return backtrack(session,tasks,sT,0);\n        \n    }\n    public int backtrack(int[] session,int[] tasks,int sT,int index){\n        \n        if(index==tasks.length){\n            \n            int temp=count(session);\n            globe=Math.min(globe,temp);\n            return temp;\n            \n        }\n        int ans=Integer.MAX_VALUE;\n        \n        //2nd optimization\n        HashSet<Integer> done=new HashSet<>();\n        \n        for(int i=1;i<=tasks.length;i++){\n            if(!done.contains(session[i]) && session[i]+tasks[index]<=sT){\n                done.add(session[i]);\n                session[i]=session[i]+tasks[index];\n                if(count(session)<globe)\n                    ans=Math.min(ans,backtrack(session,tasks,sT,index+1));\n                session[i]=session[i]-tasks[index];\n            }\n        }\n        return ans;\n    }\n    \n    // method to check the number of sessions\n    public int count(int[] session){\n        int count=0;\n        for(int a:session){\n            if(a!=0) count++;\n        }\n        return count;\n    }\n}\n```
['Backtracking', 'Java']