SDE

As there are many subproblems in the recursive solution which are solved again and again. So this problem has Overlapping Substructure property and re-computation of same subproblems can be avoided by either using Memoization or Tabulation.

The simulation of approach will make things clear: 

Input : arr[] = {3, 10, 2, 11}
LIS[] = {1, 1, 1, 1} (initially)

Iteration-wise simulation : 

arr[2] > arr[1] {LIS[2] = max(LIS [2], LIS[1]+1)=2}
arr[3] < arr[1] {No change}
arr[3] < arr[2] {No change}
arr[4] > arr[1] {LIS[4] = max(LIS [4], LIS[1]+1)=2}
arr[4] > arr[2] {LIS[4] = max(LIS [4], LIS[2]+1)=3}
arr[4] > arr[3] {LIS[4] = max(LIS [4], LIS[3]+1)=3}


Complexity Analysis: 

Time Complexity: O(n2). 
As nested loop is used.
Auxiliary Space: O(n). 
Use of any array to store LIS values at each index

Following is a simple algorithm to find out whether a given graph is Bipartite or not using Breadth First Search (BFS). 
1. Assign RED colour to the source vertex (putting into set U). 
2. Colour all the neighbours with BLUE colour (putting into set V). 
3. Colour all neighbour’s neighbour with RED colour (putting into set U). 
4. This way, assign colour to all vertices such that it satisfies all the constraints of m way colouring problem where m = 2. 
5. While assigning colours, if we find a neighbour which is coloured with same colour as current vertex, then the graph cannot be coloured with 2 vertices (or graph is not Bipartite)

The idea is to use a method similar to the merge sort algorithm. Like merge sort, divide the given array into two parts. For each left and right half, count the inversions, and at the end, sum up the inversions from both halves to get the resultant inversions.

Approach ; -

Suppose the number of inversions in the left half and right half of the array (let be inv1 and inv2); what kinds of inversions are not accounted for in Inv1 + Inv2? The answer is – the inversions that need to be counted during the merge step. Therefore, to get the total number of inversions that needs to be added are the number of inversions in the left subarray, right subarray, and merge().

Algorithm

The idea is similar to merge sort, divide the array into two equal or almost equal halves in each step until the base case is reached.
Create a function merge that counts the number of inversions when two halves of the array are merged, create two indices i and j, i is the index for the first half, and j is an index of the second half. if a[i] is greater than a[j], then there are (mid – i) inversions. because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j].
Create a recursive function to divide the array into halves and find the answer by summing the number of inversions is the first half, the number of inversion in the second half and the number of inversions by merging the two.
The base case of recursion is when there is only one element in the given half.
Print the answer

Recursively generate all the subsets and keep track of the sum of the elements in the current subset.

Subsets can be generated in the following way. For every element of the array, there are 2 options: 

Include the element in the current subset : If we include the element in the current subset, then we decrease the value of ‘K’ by the value of the element.
Do not include the element in the current subset : There is no effect on the value of ‘K’ and we can simply move onto the next element.
In any step, if the value of ‘K’ becomes 0, then we have found a subset which sums to ‘K’. We store all these subsets and return them.

I was not able to solve this question but the approach is given below.

The boundary traversal of a binary tree can be broken down into 4 parts. These parts are given in the same order as they are present in the traversal-



The root node - The root node will always be our first node in the whole boundary traversal.

The left boundary - The left most nodes of the left subtree are also included in the boundary traversal, so we will process them next except for the leaf node as it will be processed in our next part. We can use recursion for this and traverse for only left child until a leaf node is encountered. If the left child is not present we recurse for the right child.

The leaf Nodes - The leaf nodes of the binary tree will be processed next. We can use a simple inorder traversal for that. Inorder traversal will make sure that we process leaf nodes from left to right.

The right boundary - The right most nodes of the right subtree will be processed at last in reverse order except for the leaf node as it is already processed in the previous part. For this, we can use recursion in a postorder manner and traverse for the right child only until we encounter a leaf node. If the right child is not present we will recurse for the left child. The postorder recursion will make sure that we traverse the right boundary in reverse order