## Decode Ways – LeetCode Solution [Medium]

A message containing letters from A-Z can be encoded into numbers. To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping

## Greedy approach vs Dynamic Programming

Greedy approach and Dynamic programming both are used for solving optimisation problems. However often we need to use DP since optimal solution cannot be guaranteed by a greedy algorithm.

## Knapsack problem (Finding selected items)

A little recap: Let given weights & values of n items to be put in a knapsack of capacity W ie.

## Knapsack Problem (Dynamic Programming)

An optimal solution to problem contain optimal solution to subproblems. To consider all subset of items, 2 cases for every item arises

## Multiset Partitioning Problem

The number of possible partition of a set of n elements is B(n) known as Bell number. As we know, this problem is NP-Complete i.e. it has non-polynomial time solution.

## Quicksort worst-case and averages-case analysis

Quick Sort” is capable of sorting a list of data elements significantly faster (twice or thrice faster) than any of the common sorting algorithms and that’s why it is the favourite topic of interviewers.

## N Queen Problem Analysis

The N Queen is the problem of placing N chess queens on an N×N chessboard so that no two queens attack each other.

## Backtracking

Backtracking is a general algorithm for finding solutions to some computational problems, that incrementally builds candidates to the solutions, and abandons a candidate (“backtracks”) as soon as it determines that the candidate cannot possibly be completed to a valid solution.