Backtracking

Problem Mastermind is a two-player game in which the first player attempts to guess the secret code of the second. In this version, the code may be any six-digit number with all distinct digits. Each turn the first player guesses some number, and the second player responds by saying how many digits in this number correctly matched their location in the secret code. For example, if the secret code were 123456, then a guess of 175286 would score two, since 1 and 6 were correctly placed. ...

Problem Given an undirected graph represented as an adjacency matrix and an integer k, write a function to determine whether each vertex in the graph can be colored such that no two adjacent vertices share the same color using at most k colors. Examples Example 1: --- title: Input Graph --- graph LR; 0 --- 1 & 2 & 3 1 --- 2 2 --- 3 ...

Problem You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root. Examples Example 1: 10 / \ 7 15 / \ / \ 8 9 11 1 ...

Problem Given a list of words, list of single letters (might be repeating) and score of every character. Return the maximum score of any valid set of words formed by using the given letters (words[i] cannot be used two or more times). It is not necessary to use all characters in letters and each letter can only be used once. Score of letters 'a', 'b', 'c', … ,'z' is given by score[0], score[1], … , score[25] respectively. ...

Problem You are given an array nums of positive integers and a positive integer k. A subset of nums is beautiful if it does not contain two integers with an absolute difference equal to k. Return the number of non-empty beautiful subsets of the array nums. A subset of nums is an array that can be obtained by deleting some (possibly none) elements from nums. Two subsets are different if and only if the chosen indices to delete are different. ...

Problem The XOR total of an array is defined as the bitwise XOR of all its elements, or 0 if the array is empty. For example, the XOR total of the array [2,5,6] is 2 XOR 5 XOR 6 = 1. Given an array nums, return the sum of all XOR totals for every subset of nums. Note: Subsets with the same elements should be counted multiple times. ...

Problem In a gold mine grid of size m x n, each cell in this mine has an integer representing the amount of gold in that cell, 0 if it is empty. Return the maximum amount of gold you can collect under the conditions: Every time you are located in a cell you will collect all the gold in that cell. From your position, you can walk one step to the left, right, up, or down. You can’t visit the same cell more than once. Never visit a cell with 0 gold. You can start and stop collecting gold from any position in the grid that has some gold. Examples Example 1: ...

Problem Numbers can be regarded as product of its factors. For example, 8 = 2 x 2 x 2; = 2 x 4. Write a function that takes an integer n and return all possible combinations of its factors. Note: You may assume that n is always positive. Factors should be greater than 1 and less than n. Examples Example 1: ...

Problem The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once. Knight starts from chess position [0,0] generate the knight’s path. What The problem states that, given a N*M chessboard, a Knight’s Tour is defined as the sequence of moves of a Knight, such that the Knight visits every square only once. ...

kSum Problem Problem Given an array S of n integers, are there elements a1, a2, a3…ak in S such that sum(a1, a2, a3, ... ak) = target? Find all unique lists in the array which gives the sum of target. Examples Refer problems like 4Sum, 3Sum - Classic Problem, 3Sum0 - Find three elements in an array that sum to a zero for examples. ...