C++ | Sliding Window and Recursive-backtracking solution
Intuition\nI first tried to solve using recursive-backtracking approach, which obviously gave me TLE. But still my code was working for smaller inputs. \nThe be
# Intuition\nI first tried to solve using recursive-backtracking approach, which obviously gave me TLE. But still my code was working for smaller inputs. \nThe better approach I found was first sorting and updating our ans for given window size.\n\n# Approach\nStart with sorting an array, defining two pointers i and j and res variable which will get updated once we hit window size.\n\n# Complexity\n- Time complexity:\nO(n)\n\n- Space complexity:\nO(1)\n\n# Code\n```\nSliding Window Solution -\n\nclass Solution {\npublic:\n    int minimumDifference(vector<int>& nums, int k) {\n        sort(nums.begin(), nums.end());\n        int i=0, j=0;\n        int res = INT_MAX;\n        \n        for (;j<nums.size(); j++){\n            // Reached window size\n            if(j-i+1==k){\n                res = min(res, nums[j]-nums[i]);\n                i++;\n            }\n        }\n        return res;\n    }\n};\n\nRecursive-backtracking solution -\nclass Solution {\npublic:\n    int solve(int idx, int n, vector<int>& nums, vector<int>& tm, int k, int low, int high, int res){\n        if (k==0){\n            res = min(res, high-low);\n            return res;\n        }\n        int curr_low = low, curr_high=high;\n        for (int i=idx; i<n; i++){\n            // ADDING ELEMENT TO TEMP VECTOR\n            tm.push_back(nums[i]);\n            // FIND high and low for elements added till now\n            low = min(low, nums[i]);\n            high = max(high, nums[i]);\n            // cout<<low<<" "<<high<<endl;\n            // NOW SOLVE FOR REMAINING ELEMENTS\n            res = min(res, solve(i+1, n, nums, tm, k-1, low, high, res));\n            // cout<<res<<endl;\n            // REMOVE ADDED ELEMENT\n            tm.pop_back();\n            low = curr_low, high=curr_high;\n        }\n        return res;\n    }\n\n    int minimumDifference(vector<int>& nums, int k) {\n        int n=nums.size();\n        vector<int>tm;\n        int low=INT_MAX, high=INT_MIN;\n        int ans = solve(0, n, nums, tm, k, low, high, INT_MAX);\n        return ans;\n    }\n};\n```
['Backtracking', 'Recursion', 'Sliding Window', 'C++']