The longest common subsequence (LCS) problem is the problem of finding the longest subsequence common to all sequences in a set of sequences (often just two sequences).

Graph Coloring is a way of coloring the vertices of a undirected graph such that no two adjacent vertices share the same color.

The subset sum problem is a classic problem in computer science and is often solved using backtracking. The goal is to find subsets of elements selected from a given set whose sum adds up to a given number K.

Understanding the Problem

Given a set of n positive integers and a value m, the task is to determine all possible subsets whose sum is equal to m. This problem can be efficiently solved using backtracking.

Approach: Backtracking

Backtracking is a general algorithmic technique that incrementally builds candidates to a solution and abandons a candidate as soon as it is determined that the candidate cannot lead to a valid solution. In the subset sum problem, we:

1. Start with an empty subset.
2. Add elements one by one while keeping track of the sum.
3. If the sum equals m, print the subset.
4. If the sum exceeds m, backtrack and try another possibility.

The n queens puzzle is the problem of placing eight chess queens on an n×n chessboard so that no two queens threaten each other. Thus, a solution requires that no two queens share the same row, column, or diagonal.

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a mass and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.

In 0-1 Knapsack, the restriction is that, one cannot select fraction of any item. He/She must select either whole item or try with alternate one.